Methylating agents generate cytotoxic and mutagenic DNA damage. Cells use 3-methyladenine-DNA glycosylases to excise some methylated bases from DNA, and suicidal O(6)-methylguanine-DNA methyltransferases to transfer alkyl groups from other lesions onto a cysteine residue. Here we report that the highly conserved AlkB protein repairs DNA alkylation damage by means of an unprecedented mechanism. AlkB has no detectable nuclease, DNA glycosylase or methyltransferase activity; however, Escherichia coli alkB mutants are defective in processing methylation damage generated in single-stranded DNA. Theoretical protein fold recognition had suggested that AlkB resembles the Fe(ii)- and alpha-ketoglutarate-dependent dioxygenases, which use iron-oxo intermediates to oxidize chemically inert compounds. We show here that purified AlkB repairs the cytotoxic lesions 1-methyladenine and 3-methylcytosine in single- and double-stranded DNA in a reaction that is dependent on oxygen, alpha-ketoglutarate and Fe(ii). The AlkB enzyme couples oxidative decarboxylation of alpha-ketoglutarate to the hydroxylation of these methylated bases in DNA, resulting in direct reversion to the unmodified base and the release of formaldehyde.