Fucosylated glycoconjugates play a role in a wide variety of biological processes, including immune responses, signal transduction, ontogenic events and pathogenesis of several human diseases. Alpha-L-fucosidases, which are responsible for their processing, have been demonstrated to be involved in lysosomal storage disease, inflammation, cystic fibrosis, cancer development and in the interactions between gametes in vertebrates as well as invertebrates. The sequence and comparative genomic analysis of these glycosyl hydrolases and the study of their evolutionary relationships appear therefore to be of considerable interest. In this work we carried out extensive similarity searches and comparative analyses to identify sequences encoding alpha-L-fucosidases. We have identified novel alpha-L-fucosidase coding sequences in worms, insects, sea urchin, ascidians, fish, chicken, amphibians, mammals and various bacteria resulting in a total of 39 alpha-L-fucosidase sequences. Two alpha-L-fucosidases that are present in all vertebrates likely reflect a distinct biological role for paralogous genes. Comparative sequence analysis of all metazoan alpha-L-fucosidases reveals a broad conservation of features, including the aspartate residue that constitutes the catalytic nucleophile. However, a cysteine which is thought to be part of the active site is also conserved in metazoa but not in arthropods, where it is replaced by an alanine. Phylogenetic analysis suggests a gene duplication event very early in metazoan evolution with the subsequent differential loss of isoforms in various metazoan lineages.