High-entropy alloys (HEAs) have recently been applied in the field of heterogeneous catalysis benefiting from vast chemical space. However, huge chemical space also brings extreme challenges for the comprehensive study of HEAs by traditional trial-and-error experiments. Therefore, the machine learning (ML) method is presented to investigate the oxygen reduction reaction (ORR) catalytic activity of millions of reactive sites on HEA surfaces. The well-performed ML model is constructed based on the gradient boosting regression (GBR) algorithm with high accuracy, generalizability, and simplicity. In-depth analysis of the results demonstrates that adsorption energy is a mixture of the individual contributions of coordinated metal atoms near the reactive site. An efficient strategy is proposed to further boost the ORR catalytic activity of promising HEA catalysts by optimizing the HEA surface structure, which recommends a highly efficient HEA catalyst of IrPtRuRhAg. Our work offers a guide to the rational design and nanostructure synthesis of HEA catalysts.