Promiscuous substrate recognition, the ability to catalyze transformations of chemically diverse compounds, is an evolutionarily advantageous, but poorly understood phenomenon. The promiscuity of DNA repair enzymes is particularly important, because it enables diverse kinds of damage to different nucleotide bases to be repaired in a metabolically parsimonious manner. We present enzymological and crystallographic studies of the mechanisms underlying promiscuous substrate recognition by Escherichia coli AlkB, a DNA repair enzyme that removes methyl adducts and some larger alkylation lesions from endocyclic positions on purine and pyrimidine bases. In vitro Michaelis-Menten analyses on a series of alkylated bases show high activity in repairing N1-methyladenine (m1A) and N3-methylcytosine (m3C), comparatively low activity in repairing 1,N(6)-ethenoadenine, and no detectable activity in repairing N1-methylguanine or N3-methylthymine. AlkB has a substantially higher k(cat) and K(m) for m3C compared with m1A. Therefore, the enzyme maintains similar net activity on the chemically distinct substrates by increasing the turnover rate of the substrate with nominally lower affinity. Cocrystal structures provide insight into the structural basis of this "k(cat)/K(m) compensation," which makes a significant contribution to promiscuous substrate recognition by AlkB. In analyzing a large ensemble of crystal structures solved in the course of these studies, we observed 2 discrete global conformations of AlkB differing in the accessibility of a tunnel hypothesized to control diffusion of the O(2) substrate into the active site. Steric interactions between a series of protein loops control this conformational transition and present a plausible mechanism for preventing O(2) binding before nucleotide substrate binding.