The gas phase catalytic hydrodechlorination (HDC) of chlorobenzene has been studied (T = 423 K) over Pd (8 ±1 % w/w) supported on activated carbon (Pd/AC), graphite (Pd/Graphite) and graphitic carbon nanofibers (Pd/GNF). The activated carbon (875 m2 g-1) and graphite (11 m2 g-1) substrates were obtained from a commercial source but the carbon nanofibers (74 m2 g-1) were synthesized via ethylene decomposition over unsupported Ni to yield a mean fiber diameter = 225 nm. Under identical reaction conditions, the following initial HDC activity sequence has been established: Pd/GNF ≈ Pd/AC > Pd/Graphite. HDC activity declined with time-on-stream (four reaction cycles were considered) where Pd/GNF maintained a significantly higher fractional HDC and Pd/AC activity decreased continually to converge with Pd/Graphite at a common residual conversion. The pre- and post- reaction catalyst samples have been characterized by BET area/pore size analysis, TPR, TEM, SEM, H2 chemisorption/TPD, XRD and acid/base titration. Pd size distribution is given in each case where surface area-weighted Pd diameter increased in the order: Pd/Graphite < Pd/GNF < Pd/AC. The spent catalysts exhibited lower H2 uptake with a disruption to the TPD profiles. Pd on each support adopted (on the basis of XRD analysis) an exclusive cubic geometry but while the particles on AC were globular in nature, faceted Pd particles predominated on the graphite and (to a lesser extent) GNF supports. HDC activity and temporal behavior is rationalized on the basis of metal/support interaction(s), Pd particle size and H2 uptake/release characteristics. This project has been supported by the National Science Foundation.