Developing cost-effective oxygen electrocatalysts with high activity and stability is key to their commercialization. However, economical earth-abundant catalysts based on first-row transition-metal oxides suffer from low electrochemical stability, which is difficult to improve without compromising their activity. Here, using density functional theory calculations, we demonstrate that noble-metal supports lead to bifunctional enhancement of both the stability and the oxygen reduction reaction (ORR) activity of metal (oxy-hydro) oxide nanoislands. We observe a significant stabilization of supported nanoislands beyond the intrinsic stability limits of bulk phases, which originates from a favorable lattice mismatch and reductive charge transfer from oxophilic supports. We discover that interfacial active sites (located between the nanoisland and the support) reinforce the binding strength of reaction intermediates, hence boosting ORR activity. Considering that both stability and activity lead to discovery of CoOOH|Pt, NiOOH|Ag, and FeO2|Ag as viable systems for alkaline ORR, we then use a multivariant linear regression method to identify elementary descriptors for efficient screening of promising cost-effective nanoisland|support catalysts. Data Available at https://www.catalysis-hub.org/publications/BackPrediction2018.