The statistical properties of the phases of several modes nonlinearly coupled in a random system are investigated by means of a Hamiltonian model with disordered couplings. The regime in which the modes have a stationary distribution of their energies and the phases are coupled is studied for arbitrary degrees of randomness and energy. The complexity versus temperature and strength of nonlinearity is calculated. A phase diagram is derived in terms of the stored energy and amount of disorder. Implications in random lasing, nonlinear wave propagation and finite temperature Bose-Einstein condensation are discussed.