Compositionally complex materials such as high-entropy alloys and oxides have the potential to be efficient platforms for catalyst discovery because of the vast chemical space spanned by these novel materials. Identifying the composition of the most active catalyst materials, however, requires unraveling the descriptor-activity relationship, as experimentally screening the multitude of possible element ratios quickly becomes a daunting task. In this work, we show that inferred adsorption energy distributions of *OH and *O on complex solid solution surfaces within the space spanned by the system Ag−Pd−Pt−Ru are coupled to the experimentally observed electrocatalytic performance for the oxygen reduction reaction. In total, the catalytic activity of 1582 alloy compositions is predicted with a cross-validated mean absolute error of 0.042 mA/cm2 by applying a theory-derived model with only two adjustable parameters. Trends in the discrepancies between predicted electrochemical performance values of the model and the measured values on thin film surfaces subsequently provide insight into the alloys’ surface compositions during reaction conditions. Bridging this gap between computationally modeled and experimentally observed catalytic activities, not only reveals insight into the underlying theory of catalysis but also takes a step closer to realizing exploration and exploitation of high-entropy materials.