N(1)-methyladenine (m(1)A) and N(3)-methylcytosine (m(3)C) are major toxic and mutagenic lesions induced by alkylation in single-stranded DNA. In bacteria and mammals, m(1)A and m(3)C were recently shown to be repaired by AlkB-mediated oxidative demethylation, a direct DNA damage reversal mechanism. No AlkB gene homologues have been identified in Archaea. We report that m(1)A and m(3)C are repaired by the AfAlkA base excision repair glycosylase of Archaeoglobus fulgidus, suggesting a different repair mechanism for these lesions in the third domain of life. In addition, AfAlkA was found to effect a robust excision of 1,N(6)-ethenoadenine. We present a high-resolution crystal structure of AfAlkA, which, together with the characterization of several site-directed mutants, forms a molecular rationalization for the newly discovered base excision activity.