This paper demonstrates the effectiveness of a new type of hybrid nanocatalyst material that combines the high surface area of nanoparticles and nanotubes with the structural robustness and ease of handling larger supports. The hybrid material is made by fabricating palladium nanoparticles on two types of carbon supports: as-received microcellular foam (Foam) and foam with carbon nanotubes anchored on the pore walls (CNT/Foam). Catalytic reductive dechlorination of carbon tetrachloride with these materials has been investigated using gas chromatography. It is seen that while both palladium-functionalized carbon supports are highly effective in the degradation of carbon tetrachloride, the rate of degradation is significantly increased with palladium on CNT/Foam. However, there is scope to increase this rate further if the wettability of these structures can be enhanced in the future. Microstructural and spectroscopic analyses of the fresh and used catalysts have been compared which indicates that there is no change in density or surface chemical states of the catalyst after prolonged use in dechlorination test. This implies that these materials can be used repeatedly and hence provide a simple, powerful, and cost-effective approach for dechlorination of water.