We report on the first measurement of the beam-spin asymmetry in the exclusive process of coherent deeply virtual Compton scattering off a nucleus. The experiment uses the 6 GeV electron beam from the Continuous Electron Beam Accelerator Facility (CEBAF) accelerator at Jefferson Lab incident on a pressurized 4He gaseous target placed in front of the CEBAF Large Acceptance Spectrometer (CLAS). The scattered electron is detected by CLAS and the photon by a dedicated electromagnetic calorimeter at forward angles. To ensure the exclusivity of the process, a specially designed radial time projection chamber is used to detect the recoiling 4He nuclei. We measure beam-spin asymmetries larger than those observed on the free proton in the same kinematic domain. From these, we are able to extract, in a model-independent way, the real and imaginary parts of the only 4He Compton form factor, HA. This first measurement of coherent deeply virtual Compton scattering on the 4He nucleus, with a fully exclusive final state via nuclear recoil tagging, leads the way toward 3D imaging of the partonic structure of nuclei.