Hexachlorobenzene (HxCBz) owns the chemical structure of one benzene ring and six H atoms substituted by Cl atoms and it is a persistent organic pollutant present in flue gas from municipal solid waste incineration as an important precursor of dioxins. Its removal was studied using gliding arc plasma treatment, coupled downstream with a V2O5–WO3–TiO2 catalyst. Several parameters (input voltage, O2 concentration, catalytic temperature and catalyst position) all influenced its removal efficiency (RE). Optimal parameter settings were tentatively determined, i.e., an input voltage of 15 kV, the temperature of the catalyst (250 °C), and the O2 concentration (30 vol% O2) tested at a single, fixed concentration of gaseous HxCBz (71.6 ng Nm−3). A maximum RE of 76 ± 3% HxCBz was attained, with the plasma and coupled catalyst combined. Two destruction pathways, incorporating dechlorination and oxidation reactions, were recognised, both based on the detection of end- and intermediate products as well as of active species produced by the plasma. These end- and intermediate products included: low chlorinated polychlorobenzenes (mainly 1,2,4-Trichlorobenzene) as well as hydrocarbons (mainly C2H6), HCOOH, CH4, CO, CO2, etc.