Oxynitrides of cerium are expected to have many useful properties but have not been synthesized so far. We identified possible modifications of a not-yet-synthesized Ce3O3N compound, combining global search (GS) and data mining (DM) methods. Employing empirical potentials, structure candidates were obtained via global optimization on the energy landscape of Ce3O3N for different pressure values. Furthermore, additional feasible structure candidates were found using data mining of the ICSD database. The most promising structure candidates obtained were locally optimized at the ab initio level, and their E(V) curves were computed. The structure lowest in total energy, Ce3O3N-DM1, was found via local optimization starting from a data mining candidate and should be thermodynamically metastable up to high pressures.