Most polluted sites contain mixed waste. This is especially true of the U.S. Department of Energy (DOE) waste sites which hold a complex mixture of heavy metals, radionuclides, and organic solvents. In such environments enzymes that can remediate multiple pollutants are advantageous. We report here evolution of an enzyme, ChrR6 (formerly referred to as Y6), which shows a markedly enhanced capacity for remediating two of the most serious and prevalent DOE contaminants, chromate and uranyl. ChrR6 is a soluble enzyme and reduces chromate and uranyl intracellularly. Thus, the reduced product is at least partially sequestered and nucleated, minimizing the chances of reoxidation. Only one amino acid change, (Tyr)128(Asn), was responsible for the observed improvement. We show here that ChrR6 makes Pseudomonas putida and Escherichia coli more efficient agents for bioremediation if the cellular permeability barrier to the metals is decreased.