Blue-colored molybdenum oxide nitrides of the Mo-2(O,N,square)(5) type were synthesized by direct nitridation of commercially available molybdenum trioxide with a mixture of gaseous ammonia and oxygen. Chemical composition, crystal structure, and stability of the obtained and hitherto unknown compounds are studied extensively. The average oxidation state of +5 for molybdenum is proven by Mo K near-edge X-ray absorption spectroscopy; the magnetic behavior is in agreement with compounds exhibiting (MoO6)-O-v units. The new materials are stable up to similar to 773 K in an inert gas atmosphere. At higher temperatures, decomposition is observed. X-ray and neutron powder diffraction, electron diffraction, and high-resolution transmission electron microscopy reveal the structure to be related to VNb9O24.9-type phases, however, with severe disorder hampering full structure determination. Still, the results demonstrate the possibility of a future synthesis of the potential binary oxide Mo2O5. On the basis of these findings, a tentative suggestion on the crystal structure of the potential compound Mo2O5, backed by electronic-structure and phonon calculations from first principles, is given.