The distal human gut is a microbial bioreactor that digests complex carbohydrates. The strategies evolved by gut microbes to sense and process diverse glycans have important implications for the assembly and operation of this ecosystem. The human gut-derived bacterium Bacteroides thetaiotaomicron forages on both host and dietary glycans. Its ability to target these substrates resides in 88 polysaccharide utilization loci (PULs), encompassing 18% of its genome. Whole genome transcriptional profiling and genetic tests were used to define the mechanisms underlying host glycan foraging in vivo and in vitro. PULs that target all major classes of host glycans were identified. However, mucin O-glycans are the principal host substrate foraged in vivo. Simultaneous deletion of five genes encoding ECF-σ transcription factors, which activate mucin O-glycan utilization, produces defects in bacterial persistence in the gut and in mother-to-offspring transmission. Thus, PUL-mediated glycan catabolism is an important component in gut colonization and may impact microbiota ecology.