Many colonic mucosal genes that are highly regulated by microbial signals are differentially expressed along the rostral-caudal axis. This would suggest that differences in regional microbiota exist, particularly mucosa-associated microbes that are less likely to be transient. We therefore explored this possibility by examining the bacterial populations associated with the normal proximal and distal colonic mucosa in context of host Toll-like receptors (TLR) expression in C57BL/6J mice housed in specific pathogen-free (SPF) and germ-free (GF) environments. 16S rRNA gene-based terminal restriction fragment length polymorphism (T-RFLP) and clone library analysis revealed significant differences in the community structure and diversity of the mucosa-associated microbiota located in the distal colon compared to proximal colon and stool, the latter two clustering closely. Differential expression of colonic TLR2 and TLR4 along the proximal-distal axis was also found in SPF mice, but not in GF mice, suggesting that enteric microbes are essential in maintaining the regional expression of these TLRs. TLR2 is more highly expressed in proximal colon and decreases in a gradient to distal while TLR4 expression is highest in distal colon and a gradient of decreased expression to proximal colon is observed. After transfaunation in GF mice, both regional colonization of mucosa-associated microbes and expression of TLRs in the mouse colon were reestablished. In addition, exposure of the distal colon to cecal (proximal) microbiota induced TLR2 expression. These results demonstrate that regional colonic mucosa-associated microbiota determine the region-specific expression of TLR2 and TLR4. Conversely, region-specific host assembly rules are essential in determining the structure and function of mucosa-associated microbial populations. We believe this type of host-microbial mutualism is pivotal to the maintenance of intestinal and immune homeostasis.