Analytical scanning and transmission electron microscopy were used to study the microstructure of Ce,Er-doped Na0.5La0.5MoO4 laser crystals. Crystals were grown by the Czochralski method from the melts with a nominal composition of Na0.5La0.5−xCexEr0.005MoO4, where x = 0.125 and 0.15, then annealed at 700 and 1000 °C in the oxidizing atmosphere. We found the secondary phase precipitation of Ce2O3 oxide in as-grown crystals, while after high-temperature annealing the CeO2 precipitated crystals are always observed. Impurity ions Ce3+ occupy the La sites, and approximately 20% of the nominal Ce content is involved in the formation of Ce oxide secondary phase precipitates. The length of CeO2 precipitated crystals ranged between 100 nm and 550 nm (average length was 200 nm) and their width was 30–70 nm. The mechanism of CeO2 formation is discussed. The orientation relationships of Na0.5La0.5−xCexEr0.005MoO4/CeO2, the degree of coherence of the interface, and the preferential directions of their growth in the matrix were established. CeO2 crystals precipitated in the matrix cause light scattering with a wavelength comparable to the size of the precipitates and lead to deterioration of optical transparency of the material.