Haloalkane dehalogenases are key enzymes for the degradation of halogenated aliphatic pollutants. Two rhizobial strains, Mesorhizobium loti MAFF303099 and Bradyrhizobium japonicum USDA110, have open reading frames (ORFs), mlr5434 and blr1087, respectively, that encode putative haloalkane dehalogenase homologues. The crude extracts of Escherichia coli strains expressing mlr5434 and blr1087 showed the ability to dehalogenate 18 halogenated compounds, indicating that these ORFs indeed encode haloalkane dehalogenases. Therefore, these ORFs were referred to as dmlA (dehalogenase from Mesorhizobium loti) and dbjA (dehalogenase from Bradyrhizobium japonicum), respectively. The principal component analysis of the substrate specificities of various haloalkane dehalogenases clearly showed that DbjA and DmlA constitute a novel substrate specificity class with extraordinarily high activity towards β-methylated compounds. Comparison of the circular dichroism spectra of DbjA and other dehalogenases strongly suggested that DbjA contains more α-helices than the other dehalogenases. The dehalogenase activity of resting cells and Northern blot analyses both revealed that the dmlA and dbjA genes were expressed under normal culture conditions in MAFF303099 and USDA110 strain cells, respectively.