A dominant human gut microbe, the well studied symbiont Bacteroides thetaiotaomicron (Bt), is a glyco-specialist that harbors a large repertoire of genes devoted to carbohydrate processing. Despite strong similarities among them, many of the encoded enzymes have evolved distinct substrate specificities, and through the clustering of cognate genes within operons termed polysaccharide-utilization loci (PULs) enable the fulfilment of complex biological roles. Structural analyses of two glycoside hydrolase family 92 α-mannosidases, BT3130 and BT3965, together with mechanistically relevant complexes at 1.8–2.5 Å resolution reveal conservation of the global enzyme fold and core catalytic apparatus despite different linkage specificities. Structure comparison shows that Bt differentiates the activity of these enzymes through evolution of a highly variable substrate-binding region immediately adjacent to the active site. These observations unveil a genetic/biochemical mechanism through which polysaccharide-processing bacteria can evolve new and specific biochemical activities from otherwise highly similar gene products.