Active, selective and stable catalysts are imperative for sustainable energy conversion, and engineering materials with such properties are highly desired. High-entropy alloys (HEAs) offer a vast compositional space for tuning such properties. Too vast, however, to traverse without the proper tools. Here, we report the use of Bayesian optimization on a model based on density functional theory (DFT) to predict the most active compositions for the electrochemical oxygen reduction reaction (ORR) with the least possible number of sampled compositions for the two HEAs Ag-Ir-Pd-Pt-Ru and Ir-Pd-Pt-Rh-Ru. The discovered optima are then scrutinized with DFT and subjected to experimental validation where optimal catalytic activities are verified for Ag-Pd, Ir-Pt, and Pd-Ru binary alloys. This study offers insight into the number of experiments needed for optimizing the vast compositional space of multimetallic alloys which has been determined to be on the order of 50 for ORR on these HEAs.