Glyoxal is toxic and mutagenic alpha-oxoaldehyde generated in vivo as an oxidation by-product of sugar metabolism. We selected glyoxal-resistant mutants from an Escherichia coli strain lacking major glyoxal-detoxifying genes, gloA and yqhD, by growing cells in medium containing a lethal concentration of glyoxal. The mutants carried diverse genomic rearrangements, such as multibase deletions and recombination, in the upstream region of the yafB gene, encoding an aldo-keto reductase. Since these genomic lesions create transcriptional fusions of the yafB gene to the upstream rrn regulon or eliminate a negative regulatory site, the mutants generally enhanced an expression of the yafB gene. Glyoxal resistances of the mutants are correlated with the levels of yafB transcripts as well as the activities of aldo-keto reductase. An overproduction of YafB in the glyoxal-resistant mutant lacking the putative NsrR-binding site provides evidence that the yafB gene is negatively regulated by this protein. We also observed that the expression of yafB is enhanced with an increased concentration of glyoxal as well as a mutation in the fnr gene, encoding a putative regulator. The bindings of NsrR and Fnr to the yafB promoter were also demonstrated by gel mobility shift assays.