Heteroatom-doped carbon materials have been widely used in many aqueous electrocatalytic reduction reactions. Their structure-activity relationships are mainly explored based on the assumption that the doped carbon materials keep stable during electrocatalysis. Thus, the structural evolutions of heteroatom-doped carbon materials are often ignored, and their active origins are still unclear. Herein, taking N-doped graphite flake (N-GP) as the research model, we present the hydrogenation of both N and C atoms and the consequent reconstruction of the carbon skeleton during hydrogen evolution reaction (HER), accompanied by a remarkable promotion of the HER activity. The N dopants are gradually hydrogenated and almost completely dissolved in the form of ammonia. Theoretical simulations demonstrate that the hydrogenation of the N species leads to the reconstruction of the carbon skeleton from a hexagonal to a 5,7-topological ring (G5-7) with thermoneutral hydrogen adsorption and easy water dissociation. P-, S-, and Se-doped graphite also shows the similar removal of doped heteroatoms and the formation of G5-7 rings. Our work unveils the activity origin of heteroatom-doped carbon toward the HER and opens a door to the rethinking structure-performance relationships of carbon-based materials for other electrocatalytic reduction reactions.