Electrocatalytic hydrogen evolution reaction (HER) in alkaline media is important for low-cost hydrogen production in industry. Developing catalysts with ultrafast water dissociation kinetics and decent activity are main challenges for alkaline HER. Here, we report a two-step pyrolysis method to construct Ru nanoclusters uniformly deposited on nitrogen-doped graphene for efficient alkaline HER. The catalyst shows an exceptional intrinsic activity with a low overpotential of 25.9 mV at 10 mA cm−2 and a low Tafel slope of 32.6 mV dec−1 in alkaline media. Density functional theory calculations indicate that the Ru-based nanoclusters exhibit good ability for water dissociation, giving rise to the superior hydrogen evolution activity. This work shines fresh light on fabricating highly efficient catalysts for alkaline HER, as well as provides a deep insight on the reaction mechanism of Ru-based catalysts under alkaline conditions.