Vinyl chloride (VC) is a dominant carcinogenic residual in many aged chlorinated solvent plumes, and it remains a huge challenge to clean it up. Zerovalent iron (ZVI) is an effective reductant for many chlorinated compounds but shows low VC removal efficiency at field scale. Amendment of ZVI with a carbonaceous material may be used to both preconcentrate VC and facilitate redox reactions. In this study, nitrogen-doped graphene (NG) produced by a simple co-pyrolysis method using urea as nitrogen (N) source, was tested as a catalyst for VC reduction by nanoscale ZVI (nZVI). The extent of VC reduction to ethylene in the presence of 2 g/L of nZVI was less than 1% after 3 days, and barely improved with the addition of 4 g/L of graphene. In contrast, with amendment of nZVI with NG produced at pyrolysis temperature (PT) of 950 °C, the VC reduction extent increased more than 10-fold to 69%. The reactivity increased with NG PT increasing from 400 °C to an optimum at 950 °C, and it increased linearly with NG loadings. Interestingly, N dosage had little effect on reactivity if NG was produced at PT of 950 °C, while a positive correlation was observed for NG produced at PT of 600 °C. XPS and Raman analyses revealed that for NG produced at lower PT (<800 °C) mainly the content of pyridine-N-oxide (PNO) groups correlates with reactivity, while for NG produced at higher PT up to 950 °C, reactivity correlates mainly with N induced structural defects in graphene. The results of quenching and hydrogen yield experiments indicated that NG promote reduction of VC by storage of atomic hydrogen, thus increasing its availability for VC reduction, while likely also enabling electron transfer from nZVI to VC. Overall, these findings demonstrate effective chemical reduction of VC by a nZVI-NG composite, and they give insights into the effects of N doping on redox reactivity and hydrogen storage potential of carbonaceous materials.