3-Methyladenine DNA glycosylase II (AlkA) from Escherichia coli is induced in response to DNA alkylation, and it protects cells from alkylated nucleobases by catalyzing their excision. In contrast to the highly specific 3-methyladenine DNA glycosylase I (E. coli TAG) that catalyzes the excision of 3-methyl adducts of adenosine and guanosine from DNA, AlkA catalyzes the excision of a wide variety of alkylated bases including N-3 and N-7 adducts of adenosine and guanosine and O2 adducts of thymidine and cytidine. We have investigated how AlkA can recognize a diverse set of damaged bases by characterizing its discrimination between oligonucleotide substrates in vitro. Similar rate enhancements are observed for the excision of a structurally diverse set of substituted purine bases and of the normal purines adenine and guanine. These results are consistent with a remarkably indiscriminate active site and suggest that the rate of AlkA-catalyzed excision is dictated not by the catalytic recognition of a specific substrate but instead by the reactivity of the N-glycosidic bond of each substrate. Damaged bases with altered base pairing have a modest advantage, as mismatches are processed up to 400-fold faster than stable Watson-Crick base pairs. Nevertheless, AlkA does not effectively exclude undamaged DNA from its active site. The resulting deleterious excision of normal bases is expected to have a substantial cost associated with the expression of AlkA.