Ultrasmall ruthenium phosphide nanoparticles grown on reduced graphene oxide nanosheets (Ru2P/RGO-20) are reported as a highly efficient hydrogen evolution reaction (HER) catalyst. It achieves a current density of -10 mA cm-2 at extremely low overpotentials of -22 and -13 mV under acidic and alkaline conditions, respectively, superior to those of commercial Pt/C.