Palladium nanoparticles deposited on thermally oxidized silicon and on the carbon support Sibunit by the laser electrodispersion method are extremely active in the gas-phase hydrodechlorination of chlorobenzene at 100–200°C. High conversion of chlorobenzene (above 90%) has been achieved with catalysts with an unusually low metal content (from 10⁻⁴ to 10⁻³ wt %). The cyclohexane-to-benzene ratio in the reaction products depends on the process duration, palladium content, and support nature. According to X-ray photoelectron spectroscopy (XPS) data, palladium in the catalysts retains its metallic state over a long time under the reaction conditions. Possible causes of the high catalytic activity (10⁵ mol (mol Pd)⁻¹ h⁻¹) of the palladium nanoparticles and their stability to chlorination are discussed.