Gut bacteria recognize accessible glycan substrates within a complex environment. Carbohydrate binding modules (CBMs) of cell surface glycoside hydrolases often drive binding to the target substrate. Eubacterium rectale, an important butyrate-producing organism in the gut, consumes a limited range of substrates, including starch. Host consumption of resistant starch increases the abundance of E. rectale in the intestine, likely because it successfully captures the products of resistant starch degradation by other bacteria. Here, we demonstrate that the cell wall anchored starch-degrading α-amylase, Amy13K of E. rectale harbors five CBMs that all target starch with differing specificities. Intriguingly these CBMs efficiently bind to both regular and high amylose corn starch (a type of resistant starch), but have almost no affinity for potato starch (another type of resistant starch). Removal of these CBMs from Amy13K reduces the activity level of the enzyme toward corn starches by ∼40-fold, down to the level of activity toward potato starch, suggesting that the CBMs facilitate activity on corn starch and allow its utilization in vivo. The specificity of the Amy13K CBMs provides a molecular rationale for why E. rectale is able to only use certain starch types without the aid of other organisms.