Most attempts to improve the properties of high entropy alloys (HEAs) involve the exploration of non-equimolar compositions, addition of alloying elements, and/or manipulation of the microstructure. Alternatively, this work reports on intentionally doping HEAs with non-metallic species to precipitate coherent, ordered phases in order to maximize hardness. A refractory MoNbTaW HEA was synthesized via cryogenic mechanical alloying and doped with nitrogen by using liquid nitrogen as the cryogen. Overall, the doping strategy was successful as multiple nitrogen-rich secondary phases were observed. In particular, a unique ordered laminar phase was developed and identified as tetragonal (Mo,W)(Nb,Ta)N nitride via aberration-corrected scanning transmission electron microscopy (STEM). Another complex (Nb,Ta)2CN carbonitride was also identified. The growth behaviors of the ceramic phases were studied using long term aging treatments of up to 100 hours at 1200°C. A second MoNbTaW alloy was also prepared via high-energy ball milling, without nitrogen, by using liquid Ar as the cryogen. A comparison of the two alloys' microstructures and properties confirm that intentional formation of complex nitride phases greatly enhanced the hardness of mechanically alloyed MoNbTaW by up to 3-4 GPa.