We develop an adaptive machine learning strategy in search of high-performance ABO3-type cubic perovskites for catalyzing the oxygen evolution reaction (OER). The strategy has two essential components: a set of multifidelity features (e.g., composition and electronic structure) and probabilistic models with Gaussian processes trained with ab initio data for predicting activity descriptors (i.e., *O and *OH adsorption energies). By iteratively validating/refining the candidates which have theoretical overpotentials <0.5 V, albeit with large uncertainties, we attain machine learning models (RMSE < 0.5 eV) that can rapidly navigate through a chemical subspace of ∼4000 double perovskites (AA′B2O6) and single out stable structures with promising OER activity. Our approach successfully identified several known perovskites with improved catalytic performance over the benchmark LaCoO3 along with 10 other candidates that have not been reported. Importantly, by analyzing the feature distributions of better and worse catalysts than LaCoO3, we draw molecular orbital insights into physical factors governing the OER activity.