In this study, the high catalytic reactivity of ruthenium phosphide (RuP2) has been identified by first-principles density functional theory (DFT) calculations for the electrocatalytic hydrogen evolution reaction (HER). Complex surface reconstructions are considered by applying the ab initio grand canonical Monte Carlo (ai-GCMC) algorithm, efficiently providing a sufficient phase-space exploration of possible surfaces. Combined with surface-phase Pourbaix diagrams, we are able to identify the actual surfaces that obtained under specific experimental environments, thus leading to a more accurate understanding of the nature of the active sites and the binding strength of adsorbates. Specifically, through hundreds of surface reconstructions and hydrogenation states generated with ai-GCMC, we identify the most favorable surface phases of RuP2 under aqueous acidic conditions. We discover that the HER activity is determined by multiple surfaces with different stoichiometries within a narrow electrode potential window. Low HER overpotential (η) has been found for each of the identified surfaces, as low as 0.04 V. High H-coverage reconstructed surfaces have been discovered under acidic conditions, and the surface Ru sites introduced by additional Ru adatoms or exposed by P-vacancies serve as the active sites for HER based on their nearly reversible H binding. This work provides atomistic insights into the origin of high HER activity on RuP2 by exploring the dynamic surface phases of electrocatalysts and features a generalizable method to explore the reconstructed/hydrogenated surface space as a function of experimental conditions.