Despite the incredible success in reducing the overpotential of nonprecious catalysts for acidic hydrogen evolution reaction (HER) in the past few years, the stability of most platinum-free electrocatalysts is still poor. Here, we report an ultrastable electrocatalyst for acidic HER based on two-dimensional (2D) molybdenum disulfide (MoS2) doped with trace amount of palladium (<5 μg cm−2), which creates sulfur vacancies (S-vacancies). The optimized catalyst shows stable operation over 1000 h at 10 mA cm−2 with overpotential of 106 mV. The MoS2 catalyst is stabilized on a defective vertical graphene support, where the strong interaction at the 2D-2D interface increases the adhesion between the catalyst and the support. Palladium (Pd) doping generates rich sulfur vacancies in MoS2 that have a twofold role: (1) increasing hydrogen adsorption energy, which enhances activity; and (2) further increasing the adhesion between graphene support and defective MoS2, and thus enhancing stability. Complementary theoretical studies reveal the reaction pathways for substitutional doping, where the Mo-vacancy sites are prior to be doped by Pd. Our work thus offers a strategy for making stable, efficient, and earth-abundant HER catalysts with strong potential to replace platinum for PEM electrolysis.