The first observation of random laser action in a partially ordered, optically anisotropic nematic liquid crystal with long-range dielectric tensor fluctuations is reported. Above a given pump power the fluorescence curve collapses and the typical narrowing and explosion effect leads to discrete sharp peaks. The unexpected surviving of interference effects in recurrent multiple scattering provide the required optical feedback for lasing in nematics. Coherent backscattering of light waves in orientationally ordered nematic liquid crystals manifests a weak localization of light which strongly supports diffusive laser action in presence of gain medium. Intensity fluctuations of the speckle-like emission pattern indicate the typical spatio-temporal randomness of diffusive laser emission. A comparison of the laser action is reported for systems with different order degree: fully disordered semiconductor powders, self-ordered cholesterics and partially ordered nematic liquid crystals.