Chlorinated volatile organic compounds (CVOCs) are toxic chemical entities emitted invariably from stationary thermal operations when a trace of chlorine is present. Replacing the high-temperature destruction operations of these compounds with catalytic oxidation has led to the formulation of various potent metal oxides catalysts; among them are ceria-based materials. Guided by recent experimental measurements, this study theoretically investigates the initial steps operating in the interactions of ceria surface CeO2(111) with three CVOC model compounds, namely chloroethene (CE), chloroethane (CA) and chlorobenzene (CB). We find that, the CeO2(111) surface mediates fission of the carbon-chlorine bonds in the CE, CA and CB molecules via modest reaction barriers. As a result of localization of excess electrons left behind after creation of oxygen vacancies, analogous fission over an oxygen vacant surface systematically necessitates lower energy barriers. Dehydrochlorination of CE and CA molecules preferentially proceeds via a dissociative addition route; however, subsequent desorption of vinyl and ethyl moieties requires less energy than surface assisted β C-H bond breakage. The profound stability of hydrocarbon species on the surface contributes to the observed deactivation of ceria at temperatures as low as 580 K under pyrolytic conditions. Adsorption of an oxygen molecule at an oxygen vacant site initiates decomposition of the adsorbed phenyl moiety. Likewise, adsorbed surface hydroxyl groups serve as the hydrogen source in the observed conversion of CB into benzene. A plausible mechanism for the formation of 1,4-dichlorobenzene incorporates abstraction of a para hydrogen in the CB molecule by an O- surface anion followed by chlorine transfer from the surface. Plotted conversion-temperature profiles via a simplified kinetic model against corresponding experimental profiles exhibit a reasonable agreement. The results from this study could be useful in the ongoing efforts to improve ceria's catalytic capacity for destroying CVOCs.