Here we report a DFT screening study of 295 ABO2N and ABON2 PON structures composed of combinations of 55 A and B cations. Our workflow enumerates PON structures and discovers trends related to stability under reaction conditions (Figure 1). For a given pair of A-B cation oxidation states, we analyze relative stability of different anion orderings to understand composition- and configuration-dependent design rules in this chemical space. Ab initio analysis both confirms the stability of cis ordering of N and O atoms around the B-site octahedra and predicts many previously unknown PONs to be thermodynamically stable. In particular, PONs with B = {Re, Os} and a variety of A-site chemistries are predicted to be stable (i.e., a decomposition free energy of 10 meV/atom or less). Other PONs with A = {La, Nd} and B = {Nb, Ta} are also possibly stable. Theoretical Pourbaix diagrams of promising compositions are generated to understand their aqueous thermodynamic (meta)stability under varying pH and applied potentials, which has relevance to electrocatalytic applications. Generally, we find that the thermodynamic stability of PONs depends heavily on cation composition and anion ordering, leading to design guidelines to select potentially stable and synthesizable PON materials. Additionally, only a few PONs seem to be stable or metastable under acidic electrochemical conditions, suggesting that PON catalysts may function better in non-aqueous solvents for many electrochemical systems.