Catalytic hydrodechlorination (HDC) is an innovative means of transforming chlorinated waste streams into a recyclable product. In this study, the gas phase HDC of chlorobenzene (CB) has been studied over bulk Pd and Ni and ((8 ± 1) wt%) Pd and Ni supported on activated carbon (AC), graphite, graphitic nanofibers (GNF), Al2O3, and SiO2. Catalyst activation was examined by temperature-programmed reduction (TPR) analysis and the activated catalysts characterized in terms of BET area, transmission electron microscopy, scanning electron microscopy, H2 chemisorption/temperature-programmed desorption, and X-ray diffraction measurements. Metal surface area (1–19 m2/g), TPR, and H2 uptake/release exhibited a dependence on both metal and support. The Pd system delivered specific HDC rates that were up to three orders of magnitude greater than that recorded for the Ni catalysts, a result that we link to the higher H2 diffusivity in Pd. HDC was 100% selective over Ni while Pd also produced cyclohexane (selectivity < 4%) as a result of a combined HDC/hydrogenation. Bulk Pd outperformed carbon supported Pd but was less active than Pd on the oxide supports. In contrast, unsupported Ni presented no measurable activity when compared with supported Ni. The specific HDC rate was found to increase with decreasing metal surface area where spillover hydrogen served to enhance HDC performance.