Benzene contamination is a significant problem. It is used in a wide range of manufacturing processes and is a primary component of petroleum-based fuels. Benzene is a hydrocarbon that is soluble, mobile, toxic and stable, especially in ground and surface waters. It is poorly biodegraded in the absence of oxygen. However, anaerobic benzene biodegradation has been documented under various conditions. Although benzene biomineralization has been demonstrated with nitrate, Fe(III), sulphate or CO2 as alternative electron acceptors, these studies were based on sediments or microbial enrichments. Until now there were no organisms in pure culture that degraded benzene anaerobically. Here we report two Dechloromonas strains, RCB and JJ, that can completely mineralize various mono-aromatic compounds including benzene to CO2 in the absence of O2 with nitrate as the electron acceptor. This is the first example, to our knowledge, of an organism of any type that can oxidize benzene anaerobically, and we demonstrate the potential applicability of these organisms to the treatment of contaminated environments.