The application of pressure in solid-state synthesis provides a route for the creation of new and exciting materials. However, the onerous nature of high-pressure techniques limits their utility in materials discovery. The systematic search for novel oxynitrides - semiconductors for photocatalytic overall water splitting - is a representative case where quench high-pressure synthesis is useful and necessary in order to obtain target compounds. We utilize state of the art crystal structure prediction theory (USPEX) and in situ synchrotron-based X-ray scattering to speed up the discovery and optimization of novel compounds using high-pressure synthesis. Using this approach, two novel oxynitride phases were discovered in the GaN-Nb2O5 system. The (Nb2O5)0.84:(NbO2)0.32:(GaN)0.82 rutile structured phase was formed at 1 GPa and 900 °C and gradually transformed to a α-PbO2-related structure above 2.8 GPa and 1000 °C. The low-pressure rutile type phase was found to have a direct optical band gap of 0.84 eV and an indirect gap of 0.51 eV.