There is great interest in renewable and sustainable energy research to develop low-cost, highly efficient, and stable electrocatalysts as alternatives to replace Pt-based catalysts for the hydrogen evolution reaction (HER). Though nanoparticles encapsulated in carbon shells have been widely used to improve the electrode performances in energy storage devices (e.g., lithium ion batteries), they have attracted less attention in energy-related electrocatalysis. Here we report the synthesis of nitrogen-enriched core–shell structured cobalt–carbon nanoparticles dispersed on graphene sheets and we investigate their HER performances in both acidic and basic media. These catalysts exhibit excellent durability and HER activities with onset overpotentials as low as ∼70 mV in both acidic (0.5 M H2SO4) and alkaline (0.1 M NaOH) electrolytes, and the overpotentials needed to deliver 10 mA cm–2 are determined to be 265 mV in acid and 337 mV in base, further demonstrating their potential to replace Pt-based catalysts. Control experiments reveal that the active sites for HER might come from the synergistic effects between the cobalt nanoparticles and nitrogen-doped carbon.