The first measurement of the beam-spin asymmetry in exclusive electroproduction of real photons in the deeply inelastic regime was performed. A large asymmetry with sinφ modulation was observed as predicted by the interference of deeply virtual Compton scattering (DVCS) and the Bethe-Heitler process. The amplitude of the modulation was calculated to be about α=0.202±0.028. α was found to be directly proportional to the imaginary part of the DVCS amplitude, in leading-order and leading-twist perturbative quantum chromodynamic (QCD) corrections.