The iron(II)- and 2-oxoglutarate (2OG)-dependent dioxygenase AlkB from Escherichia coli (EcAlkB) repairs alkylation damage in DNA by direct reversal. EcAlkB substrates include methylated bases, such as 1-methyladenine (m(1)A) and 3-methylcytosine (m(3)C), as well as certain bulkier lesions, for example the exocyclic adduct 1,N(6)-ethenoadenine (epsilonA). EcAlkB is the only bacterial AlkB protein characterized to date, and we here present an extensive bioinformatics and functional analysis of bacterial AlkB proteins. Based on sequence phylogeny, we show that these proteins can be subdivided into four groups: denoted 1A, 1B, 2A and 2B; each characterized by the presence of specific conserved amino acid residues in the putative nucleotide-recognizing domain. A scattered distribution of AlkB proteins from the four different groups across the bacterial kingdom indicates a substantial degree of horizontal transfer of AlkB genes. DNA repair activity was associated with all tested recombinant AlkB proteins. Notably, both a group 2B protein from Xanthomonas campestris and a group 2A protein from Rhizobium etli repaired etheno adducts, but had negligible activity on methylated bases. Our data indicate that the majority, if not all, of the bacterial AlkB proteins are DNA repair enzymes, and that some of these proteins do not primarily target methylated bases.