High-entropy alloys (HEAs) have intriguing material properties, but their potential as catalysts has not been widely explored. Based on a concise theoretical model, we predict that the surface of a quaternary HEA of base metals, CoCrFeNi, should go from being nearly fully oxidized except for pure Ni sites when exposed to O2 to being partially oxidized in an acidic solution under cathodic bias, and that such a partially oxidized surface should be more active for the electrochemical hydrogen evolution reaction (HER) in acidic solutions than all the component metals. These predictions are confirmed by electrochemical and surface science experiments: the Ni in the HEA is found to be most resistant to oxidation, and when deployed in 0.5 M H2SO4, the HEA exhibits an overpotential of only 60 mV relative to Pt for the HER at a current density of 1 mA/cm2.