The replacement of platinum with non-precious-metal electrocatalysts with high efficiency and superior stability for the hydrogen-evolution reaction (HER) remains a great challenge. Herein, we report the one-step synthesis of uniform, ultrafine molybdenum carbide (Mo2C) nanoparticles (NPs) within a carbon matrix from inexpensive starting materials (dicyanamide and ammonium molybdate). The optimized catalyst consisting of Mo2C NPs with sizes lower than 3 nm encapsulated by ultrathin graphene shells (ca. 1-3 layers) showed superior HER activity in acidic media, with a very low onset potential of -6 mV, a small Tafel slope of 41 mV dec(-1), and a large exchange current density of 0.179 mA cm(-2), as well as good stability during operation for 12 h. These excellent properties are similar to those of state-of-the-art 20% Pt/C and make the catalyst one of the most active acid-stable electrocatalysts ever reported for HER.