Bifidobacteria are predominant bacteria present in the intestines of breast-fed infants and offer important health benefits for the host. Human milk oligosaccharides are one of the most important growth factors for bifidobacteria and are frequently fucosylated at their non-reducing termini. Previously, we identified 1,2-alpha-l-fucosidase (AfcA) belonging to the novel glycoside hydrolase (GH) family 95, from Bifidobacterium bifidum JCM1254 (Katayama T, Sakuma A, Kimura T, Makimura Y, Hiratake J, Sakata K, Yamanoi T, Kumagai H, Yamamoto K. 2004. Molecular cloning and characterization of Bifidobacterium bifidum 1,2-alpha-l-fucosidase (AfcA), a novel inverting glycosidase (glycoside hydrolase family 95). J Bacteriol. 186:4885-4893). Here, we identified a gene encoding a novel 1,3-1,4-alpha-l-fucosidase from the same strain and termed it afcB. The afcB gene encodes a 1493-amino acid polypeptide containing an N-terminal signal sequence, a GH29 alpha-l-fucosidase domain, a carbohydrate binding module (CBM) 32 domain, a found-in-various-architectures (FIVAR) domain and a C-terminal transmembrane region, in this order. The recombinant enzyme was expressed in Escherichia coli and was characterized. The enzyme specifically released alpha1,3- and alpha1,4-linked fucosyl residues from 3-fucosyllactose, various Lewis blood group substances (a, b, x, and y types), and lacto-N-fucopentaose II and III. However, the enzyme did not act on glycoconjugates containing alpha1,2-fucosyl residue or on synthetic alpha-fucoside (p-nitrophenyl-alpha-l-fucoside). The afcA and afcB genes were introduced into the B. longum 105-A strain, which has no intrinsic alpha-l-fucosidase. The transformant carrying afcA could utilize 2'-fucosyllactose as the sole carbon source, whereas that carrying afcB was able to utilize 3-fucosyllactose and lacto-N-fucopentaose II. We suggest that AfcA and AfcB play essential roles in degrading alpha1,2- and alpha1,3/4-fucosylated milk oligosaccharides, respectively, and also glycoconjugates, in the gastrointestinal tracts.