A single-electron transistor incorporated as part of a nanomechanical resonator represents an extreme limit of electron-phonon coupling. While it allows for fast and sensitive electromechanical measurements, it also introduces backaction forces from electron tunnelling which randomly perturb the mechanical state. Despite the stochastic nature of this backaction, under conditions of strong coupling it is predicted to create self-sustaining coherent mechanical oscillations. Here, we verify this prediction using time-resolved measurements of a vibrating carbon nanotube transistor. This electromechanical oscillator has intriguing similarities with a laser. The single-electron transistor, pumped by an electrical bias, acts as a gain medium while the resonator acts as a phonon cavity. Despite the unconventional operating principle, which does not involve stimulated emission, we confirm that the output is coherent, and demonstrate other laser behaviour including injection locking and frequency narrowing through feedback.