Mammals harbor a complex gut microbiome, comprised of bacteria that confer immunologic, metabolic and neurologic benefits1. Despite advances in sequence-based microbial profiling and myriad studies defining microbiome composition during health and disease, little is known about the molecular processes employed by symbiotic bacteria to stably colonize the gastrointestinal (GI) tract. We sought to define how mammals assemble and maintain the Bacteroides, one of the most numerically prominent genera of the human microbiome. While the gut normally contains hundreds of bacterial species2,3, we surprisingly find that germ-free mice mono-associated with a single Bacteroides are resistant to colonization by the same, but not different, species. To identify bacterial mechanisms for species-specific saturable colonization, we devised an in vivo genetic screen and discovered a unique class of Polysaccharide Utilization Loci (PUL) that are conserved among intestinal Bacteroides. We named this genetic locus the commensal colonization factors (ccf). Deletion of the ccf genes in the model symbiont, Bacteroides fragilis, results in colonization defects in mice and reduced horizontal transmission. The ccf genes of B. fragilis are up-regulated during gut colonization, preferentially at the colonic surface. When we visualize microbial biogeography within the colon, B. fragilis penetrates the colonic mucus and resides deep within crypt channels, while ccf mutants are defective in crypt association. Remarkably, the CCF system is required for B. fragilis colonization following microbiome disruption with Citrobacter rodentium infection or antibiotic treatment, suggesting the niche within colonic crypts represents a reservoir for bacteria to maintain long-term colonization. These findings reveal that intestinal Bacteroides have evolved species-specific physical interactions with the host that mediate stable and resilient gut colonization, and the CCF system represents a novel molecular mechanism for symbiosis.