Toluene and other fuel hydrocarbons are commonly found in association with radionuclides at numerous US Department of Energy sites, frequently occurring together with Cr(VI) and other heavy metals. In this study, the extremely radiation-resistant bacterium Deinococcus radiodurans, which naturally reduces Cr(VI) to the less mobile and less toxic Cr(III), was engineered for complete toluene degradation by cloned expression of tod and xyl genes of Pseudomonas putida. The recombinant Tod/Xyl strain showed incorporation of carbon from 14C-labelled toluene into cellular macromolecules and carbon dioxide, in the absence or presence of chronic ionizing radiation. The engineered bacteria were able to oxidize toluene under both minimal and complex nutrient conditions, and recombinant cells reduced Cr(VI) in sediment microcosms. As such, the Tod/Xyl strain could provide a model for examining the reduction of metals coupled to organic contaminant oxidation in aerobic radionuclide-contaminated sediments.