The availability and repartition of fucosylated glycans within the gastrointestinal tract contributes to the adaptation of gut bacteria species to ecological niches. To access this source of nutrients, gut bacteria encode α-L-fucosidases (fucosidases) which catalyze the hydrolysis of terminal α-L-fucosidic linkages. We determined the substrate and linkage specificities of fucosidases from the human gut symbiont Ruminococcus gnavus. Sequence similarity network identified strain-specific fucosidases in R. gnavus ATCC 29149 and E1 strains that were further validated enzymatically against a range of defined oligosaccharides and glycoconjugates. Using a combination of glycan microarrays, mass spectrometry, isothermal titration calorimetry, crystallographic and saturation transfer difference NMR approaches, we identified a fucosidase with the capacity to recognize sialic acid-terminated fucosylated glycans (sialyl Lewis X/A epitopes) and hydrolyze α1-3/4 fucosyl linkages in these substrates without the need to remove sialic acid. Molecular dynamics simulation and docking showed that 3'-Sialyl Lewis X (sLeX) could be accommodated within the binding site of the enzyme. This specificity may contribute to the adaptation of R. gnavus strains to the infant and adult gut and has potential applications in diagnostic glycomic assays for diabetes and certain cancers.