A new phase of black color, cerium niobium oxynitride with general formula CeNb(O,N)3, was synthesized by thermal ammonolysis, and its crystal structure and physical and chemical properties are investigated. Powder X-ray and neutron diffraction has confirmed the perovskite-structured CeNbO1.49(7)N1.51(7) phase crystallized with the orthorhombic Pnma symmetry with unit cell parameters of a = 5.7137(5) Å, b = 8.0567(5) Å, c = 5.7209(5) Å, presenting a partially ordered anionic arrangement. The incorporation of nitrogen into the oxygen sublattice was confirmed by X-ray photoelectron spectroscopy. Complex multistage redox processes of this material at elevated temperatures in air, including full amorphization above 200 °C, recrystallization at 650 °C, decomposition at 950 °C, and a final oxidation into the stoichiometric cerium niobium oxide CeNbO4, were observed by simultaneous thermal analysis and in situ X-ray powder diffraction. The band gap of the oxynitride material was investigated by UV–vis spectroscopy and, due to the incorporation of nitrogen into the oxygen sublattice, a significant decrease from Eg = 2.67 eV for the precursor oxide CeNbO4+δ to Eg = 1.79 eV was observed. The simulation by density functional theory further confirms that the partially ordered anionic arrangement widens the band gap (1.78 eV) and stabilizes the structure compared to the completely ordered (layered) structure (1.22 eV).