Oxygen electrocatalysis plays a key role in many promising renewable electrochemical energy storage and conversion technologies such as fuel cells and electrolyzers. The energy efficiencies of these technologies have been hampered by the sluggish kinetics of oxygen-based (oxygen evolution reaction-OER and oxygen reduction reaction-ORR) electrochemical reactions and consequently demand a high overpotential to drive these reactions, even when using state–of–the–art oxygen electrocatalysts. Moreover, the stability of these materials should be on par with their catalytic activity to develop electrocatalysts for practical applications. Herein, we use computational Pourbaix diagrams to identify acid stable non–binary oxide materials by analyzing the aqueous stability of oxides in the Materials Project database at pH = 0 under typical potential ranges of 0.6 – 1.0 V (vs. SHE) and 1.2 – 2.0 V (vs. SHE) for ORR and OER, respectively. Then we performed a systematic high-throughput screening of the ORR and OER activity of these stable materials by determining unique surface terminations and active sites, incorporating surface coverages of the reaction intermediates under reaction conditions, and calculating adsorption free energies of reaction intermediates to predict theoretical ORR-limiting potentials and OER overpotentials. These calculations predicted that first-row transition metal antimonates (MSbOx, M=Mn, Fe, Ni, Co) have desirable ORR and OER performance characteristics. Moreover, the effect of introducing transition metals on the activity of these MSbOx is studied using computational methods and demonstrates the viability of nanoscale ternary and quaternary systems in this family. Finally, on the basis of theoretical and experimental findings, rational catalyst design principles for next-generation oxygen electrocatalysts are established.