Perovskite oxynitrides (PONs), derivatives of the perovskite oxide structure with both N and O anions, show great promise as catalysts in electrochemical and photochemical reactions. Their versatility arises largely from a high degree of geometric and electronic structure tunability, achievable laregly through anion and cation ordering and composition. There are potentially tens of thousands of PON structures. However, little is known about which are synthesizable or stable under electrochemical reaction conditions, or the trends in anion or cation choice that could predict this stability. Here we conduct a high-throughput DFT screening study of 295 ABO2N and ABON2 PON structures composed of combinations of 55 cations. We hypothesized that anion orderings with cis ordering of the anions and particular cations in a PON structure would correspond to a low calculated decomposition energy. We identified 32 possible symmetrically distinct anion orderings and found that orderings with both a high fraction of M-B-M cis bonds (M = N for ABO2N and O for ABON2) and a high distribution of these bonds throughout the structure generally lead to stable PON structures. We found that PONs with B = {Re, Os} are predicted to be especially stable, with some A = {La, Nd} compounds also predicted to have high stability. Our work suggests that formability of PONs indeed relies on cation and anion engineering and establishes design guidelines for selecting and synthesizing stable PON materials. Our methodology also provides an impotant filtering step to focus future high-throughput materials studies towards promising and stable candidates.