We investigate mode-locking processes in lasers displaying a variable degree of structural randomness. By a spin-glass theoretic approach, we analyze the mean-field Hamiltonian and derive a phase diagram in terms of pumping rate and degree of disorder. Paramagnetic (noisy continuous wave emission), ferromagnetic (standard passive mode locking), and spin-glass phases with an exponentially large number of configurations are identified. The results are also relevant for other physical systems displaying a random Hamiltonian, such as Bose-condensed gases and nonlinear optics.