The hydrogen evolution reaction (HER) is a fundamental process in electrocatalysis and plays an important role in energy conversion through water splitting to produce hydrogen. Effective candidates for HER are often based on noble metals or transition metal dichalcogenides, while carbon-based metal-free electrocatalysts generally demonstrate poorer activity. Here we report evaluation of a series of heteroatom-doped graphene materials as efficient HER electrocatalysts by combining spectroscopic characterization, electrochemical measurements, and density functional theory calculations. Results of theoretical computations are shown to be in good agreement with experimental observations regarding the intrinsic electrocatalytic activity and the HER reaction mechanism. As a result, we establish a HER activity trend for graphene-based materials, and explore their reactivity origin to guide the design of more efficient electrocatalysts. We predict that by rationally modifying particular experimentally achievable physicochemical characteristics, a practically realizable graphene-based material will have the potential to exceed the performance of the metal-based benchmark for HER.