Reduction of water to hydrogen through electrocatalysis holds great promise for clean energy, but its large-scale application relies on the development of inexpensive and efficient catalysts to replace precious platinum catalysts. Here we report an electrocatalyst for hydrogen generation based on very small amounts of cobalt dispersed as individual atoms on nitrogen-doped graphene. This catalyst is robust and highly active in aqueous media with very low overpotentials (30 mV). A variety of analytical techniques and electrochemical measurements suggest that the catalytically active sites are associated with the metal centres coordinated to nitrogen. This unusual atomic constitution of supported metals is suggestive of a new approach to preparing extremely efficient single-atom catalysts.