Methylating agents introduce cytotoxic 1-methyladenine (1-meA) and 3-methylcytosine (3-meC) residues into nucleic acids, and it was recently demonstrated that the Escherichia coli AlkB protein and two human homologues, hABH2 and hABH3, can remove these lesions from DNA by oxidative demethylation. Moreover, AlkB and hABH3 were also found to remove 1-meA and 3-meC from RNA, suggesting that cellular RNA repair can occur. We have here studied the preference of AlkB, hABH2 and hABH3 for single-stranded DNA (ssDNA) or double-stranded DNA (dsDNA), and show that AlkB and hABH3 prefer ssDNA, while hABH2 prefers dsDNA. This was consistently observed with three different oligonucleotide substrates, implying that the specificity for single-stranded versus double-stranded DNA is sequence independent. The dsDNA preference of hABH2 was observed only in the presence of magnesium. The activity of the enzymes on single-stranded RNA (ssRNA), double-stranded RNA (dsRNA) and DNA/RNA hybrids was also investigated, and the results generally confirm the notion that while AlkB and hABH3 tend to prefer single-stranded nucleic acids, hABH2 is more active on double-stranded substrates. These results may contribute to identifying the main substrates of bacterial and human AlkB proteins in vivo.