l-Fucose is the most widely distributed l-hexose in marine and terrestrial environments, and presents a variety of functional roles. l-Fucose is the major monosaccharide in the polysaccharide fucoidan from cell walls of brown algae, and is found in human milk oligosaccharides and the Lewis blood group system, where it is important in cell signaling and immune response stimulation. Removal of fucose from these biomolecules is catalyzed by fucosidases belonging to different carbohydrate-active enzyme (CAZy) families. Fucosidases of glycoside hydrolase family 29 (GH29) release α-l-fucose from non-reducing ends of glycans and display activities targeting different substrate compositions and linkage types. While several GH29 fucosidases from terrestrial environments have been characterized, much less is known about marine members of GH29 and their substrate specificities, as only four marine GH29 enzymes were previously characterized. Here, five GH29 fucosidases originating from an uncultured fucoidan-degrading marine bacterium (Paraglaciecola sp.) were cloned and produced recombinantly in E. coli. All five enzymes (Fp231, Fp239, Fp240, Fp251, Fp284) hydrolyzed the synthetic substrate CNP-α-l-fucose. Assayed against up to 17 fucose-containing oligosaccharides, Fp239 showed activity against the Lewis Y antigen, 2'- and 3-fucosyllactose while Fp284 degraded 2'-fucosyllactose and Fuc(α1,6)GlcNAc. Furthermore, Fp231 displayed strict specificity against Fuc(α1,4)GlcNAc, a previously unreported specificity in GH29. Fp231 is a monomeric enzyme with pH and temperature optima at pH 5.6-6.0 and 25 °C, hydrolyzing Fuc(α1,4)GlcNAc with kcat = 1.3 s-1 and Km = 660 μM. Altogether, the findings extend our knowledge about GH29 family members from the marine environment, which are so far largely unexplored.