Palladium catalysts (0.5 and 1 wt%) supported on carbon nanofibres were prepared and tested for tetrachloroethylene (TTCE) catalytic hydrodechlorination working with high organic loadings (using TTCE/toluene mixture, 0.9 M, that simulate real chlorinated wastes). For comparison, a commercial 0.5%-Pd/activated carbon catalyst was also tested for this reaction. CNF-based catalysts showed lower initial activity than the activated carbon-supported catalyst (40% vs. 60% initial conversion) but higher stability (after 25 h on stream activated carbon-based catalyst is completely deactivated whereas CNF-based catalysts show activities of about 15%). The fresh and used catalysts were characterized by BET, TEM, SEM, XRD and XPS. Results obtained suggest that the catalyst deactivation is caused by a combination of coke formation (lower amounts than in the case of conventional supports), and chlorine-poisoning.