Mononuclear iron-containing oxygenases conduct a diverse variety of oxidation functions in biology, including the oxidative demethylation of methylated nucleic acids and histones. Escherichia coli AlkB is the first such enzyme that was discovered to repair methylated nucleic acids, which are otherwise cytotoxic and/or mutagenic. AlkB human homologues are known to play pivotal roles in various processes. Here we present structural characterization of oxidation intermediates for these demethylases. Using a chemical cross-linking strategy, complexes of AlkB-double stranded DNA (dsDNA) containing 1,N(6)-etheno adenine (εA), N(3)-methyl thymine (3-meT) and N(3)-methyl cytosine (3-meC) are stabilized and crystallized, respectively. Exposing these crystals, grown under anaerobic conditions containing iron(II) and α-ketoglutarate (αKG), to dioxygen initiates oxidation in crystallo. Glycol (from εA) and hemiaminal (from 3-meT) intermediates are captured; a zwitterionic intermediate (from 3-meC) is also proposed, based on crystallographic observations and computational analysis. The observation of these unprecedented intermediates provides direct support for the oxidative demethylation mechanism for these demethylases. This study also depicts a general mechanistic view of how a methyl group is oxidatively removed from different biological substrates.