Mode locking, the self-starting synchronous oscillation of electromagnetic modes in a laser cavity, is the primary way to generate ultrashort light pulses. In random lasers, without a cavity, mode-locking, the nonlinear coupling amongst low spatially coherent random modes, can be activated via optical pumping, even without the emission of short pulses. Here, by exploiting the combination of the inherently giant third-order χ(3) nonlinearity of semiconductor heterostructure lasers and the nonlinear properties of graphene, the authors demonstrate mode-locking in surface-emitting electrically pumped random quantum cascade lasers at terahertz frequencies. This is achieved by either lithographically patterning a multilayer graphene film to define a surface random pattern of light scatterers, or by coupling on chip a saturable absorber graphene reflector. Intermode beatnote mapping unveils self-induced phase-coherence between naturally incoherent random modes. Self-mixing intermode spectroscopy reveals phase-locked random modes. This is an important milestone in the physics of disordered systems. It paves the way to the development of a new generation of miniaturized, electrically pumped mode-locked light sources, ideal for broadband spectroscopy, multicolor speckle-free imaging applications, and reservoir quantum computing.