Isomaltooligosaccharides (IMO) have been suggested as promising prebiotics that stimulate the growth of probiotic bacteria. Genomes of probiotic lactobacilli from the acidophilus group, as represented by Lactobacillus acidophilus NCFM, encode α-1,6 glucosidases of the family GH13_31 (glycoside hydrolase family 13 subfamily 31) that confer degradation of IMO. These genes reside frequently within maltooligosaccharide utilization operons, which include an ATP-binding cassette transporter and α-glucan active enzymes, e.g., maltogenic amylases and maltose phosphorylases, and they also occur separated from any carbohydrate transport or catabolism genes on the genomes of some acidophilus complex members, as in L. acidophilus NCFM. Besides the isolated locus encoding a GH13_31 enzyme, the ABC transporter and another GH13 in the maltooligosaccharide operon were induced in response to IMO or maltotetraose, as determined by reverse transcription-PCR (RT-PCR) transcriptional analysis, suggesting coregulation of α-1,6- and α-1,4-glucooligosaccharide utilization loci in L. acidophilus NCFM. The L. acidophilus NCFM GH13_31 (LaGH13_31) was produced recombinantly and shown to be a glucan 1,6-α-glucosidase active on IMO and dextran and product-inhibited by glucose. The catalytic efficiency of LaGH13_31 on dextran and the dextran/panose (trisaccharide) efficiency ratio were the highest reported for this class of enzymes, suggesting higher affinity at distal substrate binding sites. The crystal structure of LaGH13_31 was determined to a resolution of 2.05 Å and revealed additional substrate contacts at the +2 subsite in LaGH13_31 compared to the GH13_31 from Streptococcus mutans (SmGH13_31), providing a possible structural rationale to the relatively high affinity for dextran. A comprehensive phylogenetic and activity motif analysis mapped IMO utilization enzymes from gut microbiota to rationalize preferential utilization of IMO by gut residents.