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