Glycan utilization plays a key role in modulating the composition of the gut microbiota, but molecular insight into oligosaccharide uptake by this microbial community is lacking. Arabinoxylo‐oligosaccharides (AXOS) are abundant in the diet, and are selectively fermented by probiotic bifidobacteria in the colon. Here we show how selectivity for AXOS uptake is established by the probiotic strain Bifidobacterium animalis subsp. lactis Bl‐04. The binding protein BlAXBP, which is associated with an ATP‐binding cassette (ABC) transporter that mediates the uptake of AXOS, displays an exceptionally broad specificity for arabinosyl‐decorated and undecorated xylo‐oligosaccharides, with preference for tri‐ and tetra‐saccharides. Crystal structures of BlAXBP in complex with four different ligands revealed the basis for this versatility. Uniquely, the protein was able to recognize oligosaccharides in two opposite orientations, which facilitates the optimization of interactions with the various ligands. Broad substrate specificity was further enhanced by a spacious binding pocket accommodating decorations at different mainchain positions and conformational flexibility of a lid‐like loop. Phylogenetic and genetic analyses show that BlAXBP is highly conserved within Bifidobacterium, but is lacking in other gut microbiota members. These data indicate niche adaptation within Bifidobacterium and highlight the metabolic syntrophy (cross‐feeding) among the gut microbiota.