We demonstrated that heteroatomic nitrogen (N) doping of graphene can significantly enhance the performance of the graphene-palladium nanoparticle composite catalyst (N/G-Pd) in the electrocatalytic hydrodechlorination (EHDC) reaction. Specifically at -0.80 V (vs. Ag/AgCl), the N/G-430-Pd (prepared at 430 °C, pyridinic/pyrrolic-N-rich) and N/G-900-Pd (prepared at 900 °C, pyridinic/graphitic-N-rich) with equivalent total N content delivered the apparent rate constants (kobs) of 0.28 and 0.20 min-1 molPd-1 in removing 2,4-dichlorophenol, much higher than the 0.13 min-1 molPd-1 of the C-Pd. Additionally, we identified the determinant role of pyrrolic-N in boosting EHDC from the linear relationship between kobs-N and the pyrrolic-N content in the catalyst. Combined experimental and DFT analyses revealed that the positive effect of N doping originated from the strong N-Pd interactions, which modulated the Pd electronic structure and its interactions with the reactant and EHDC products (phenol and Cl-). The pyrrolic N-Pd bond was favorable as it could balance the reactant adsorption and the product desorption.