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 He4 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 He4 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 He4 Compton form factor, HA. This first measurement of coherent deeply virtual Compton scattering on the He4 nucleus, with a fully exclusive final state via nuclear recoil tagging, leads the way toward 3D imaging of the partonic structure of nuclei.