Understanding random lasing is a formidable theoretical challenge. Unlike conventional lasers, random lasers have no resonator to trap light, they are highly multimode with potentially strong modal interactions, and they are based on disordered gain media, where photons undergo random multiple scattering. Interference effects notoriously modify the propagation of waves in such random media, but their fate in the presence of nonlinearity and interactions is poorly understood. Here, we present a semiclassical theory for multimode random lasing in the strongly scattering regime. We show that Anderson localization, a wave interference effect, is not affected by the presence of nonlinearities. To the contrary, its presence suppresses interactions between simultaneously lasing modes. Consequently, each lasing mode in a strongly scattering random laser is given by a single long-lived, Anderson localized mode of the passive cavity, the frequency and wave profile of which do not vary with pumping, even in the multimode regime when modes spatially overlap.