AbstractHaloalkane dehalogenases (HLDs) are enzymes that catalyze the cleavage of carbon–halogen bonds by a hydrolytic mechanism. Although comparative biochemical analyses have been published, no classification system has been proposed for HLDs, to date, that reconciles their phylogenetic and functional relationships. In the study presented here, we have analyzed all sequences and structures of genuine HLDs and their homologs detectable by database searches. Phylogenetic analyses revealed that the HLD family can be divided into three subfamilies denoted HLD‐I, HLD‐II, and HLD‐III, of which HLD‐I and HLD‐III are predicted to be sister‐groups. A mismatch between the HLD protein tree and the tree of species, as well as the presence of more than one HLD gene in a few genomes, suggest that horizontal gene transfers, and perhaps also multiple gene duplications and losses have been involved in the evolution of this family. Most of the biochemically characterized HLDs are found in the HLD‐II subfamily. The dehalogenating activity of two members of the newly identified HLD‐III subfamily has only recently been confirmed, in a study motivated by this phylogenetic analysis. A novel type of the catalytic pentad (Asp‐His‐Asp+Asn‐Trp) was predicted for members of the HLD‐III subfamily. Calculation of the evolutionary rates and lineage‐specific innovations revealed a common conserved core as well as a set of residues that characterizes each HLD subfamily. The N‐terminal part of the cap domain is one of the most variable regions within the whole family as well as within individual subfamilies, and serves as a preferential site for the location of relatively long insertions. The highest variability of discrete sites was observed among residues that are structural components of the access channels. Mutations at these sites modify the anatomy of the channels, which are important for the exchange of ligands between the buried active site and the bulk solvent, thus creating a structural basis for the molecular evolution of new substrate specificities. Our analysis sheds light on the evolutionary history of HLDs and provides a structural framework for designing enzymes with new specificities. Proteins 2007. © 2007 Wiley‐Liss, Inc.