Methylating agents generate cytotoxic and mutagenic DNA damage. Cells use 3-methyladenine-DNA glycosylases to excise some methylated bases from DNA, and suicidal O⁶-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 α-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, α-ketoglutarate and Fe(ii). The AlkB enzyme couples oxidative decarboxylation of α-ketoglutarate to the hydroxylation of these methylated bases in DNA, resulting in direct reversion to the unmodified base and the release of formaldehyde.