Soil bacteria are heavily exposed to environmental methylating agents such as methylchloride and may have special requirements for repair of alkylation damage on DNA. We have used functional complementation of an Escherichia coli tag alkA mutant to screen for 3-methyladenine DNA glycosylase genes in genomic libraries of the soil bacterium Bacillus cereus. Three genes were recovered: alkC, alkD and alkE. The amino acid sequence of AlkE is homologous to the E. coli AlkA sequence. AlkC and AlkD represent novel proteins without sequence similarity to any protein of known function. However, iterative and indirect sequence similarity searches revealed that AlkC and AlkD are distant homologues of each other within a new protein superfamily that is ubiquitous in the prokaryotic kingdom. Homologues of AlkC and AlkD were also identified in the amoebas Entamoeba histolytica and Dictyostelium discoideum, but no other eukaryotic counterparts of the superfamily were found. The alkC and alkD genes were expressed in E. coli and the proteins were purified to homogeneity. Both proteins were found to be specific for removal of N-alkylated bases, and showed no activity on oxidized or deaminated base lesions in DNA. B. cereus AlkC and AlkD thus define novel families of alkylbase DNA glycosylases within a new protein superfamily.