The desire for improved methods of biomass conversion into fuels and feedstocks has re-awakened interest in the enzymology of plant cell wall degradation. The complex polysaccharide xyloglucan is abundant in plant matter, where it may account for up to 20% of the total primary cell wall carbohydrates. Despite this, few studies have focused on xyloglucan saccharification, which requires a consortium of enzymes including endo-xyloglucanases, α-xylosidases, β-galactosidases and α-L-fucosidases, among others. In the present paper, we show the characterization of Xyl31A, a key α-xylosidase in xyloglucan utilization by the model Gram-negative soil saprophyte Cellvibrio japonicus. CjXyl31A exhibits high regiospecificity for the hydrolysis of XGOs (xylogluco-oligosaccharides), with a particular preference for longer substrates. Crystallographic structures of both the apo enzyme and the trapped covalent 5-fluoro-β-xylosyl-enzyme intermediate, together with docking studies with the XXXG heptasaccharide, revealed, for the first time in GH31 (glycoside hydrolase family 31), the importance of a PA14 domain insert in the recognition of longer oligosaccharides by extension of the active-site pocket. The observation that CjXyl31A was localized to the outer membrane provided support for a biological model of xyloglucan utilization by C. japonicus, in which XGOs generated by the action of a secreted endo-xyloglucanase are ultimately degraded in close proximity to the cell surface. Moreover, the present study diversifies the toolbox of glycosidases for the specific modification and saccharification of cell wall polymers for biotechnological applications.