Environmental influences (infections and diet) strongly affect a host's microbiota. However, host genetics may influence commensal communities, as suggested by the greater similarity between the microbiomes of identical twins compared to non-identical twins. Variability of human genomes and microbiomes complicates the understanding of polymorphic mechanisms regulating the commensal communities. Whereas animal studies allow genetic modifications, they are sensitive to influences known as "cage" or "legacy" effects. Here, we analyze ex-germ-free mice of various genetic backgrounds, including immunodeficient and major histocompatibility complex (MHC) congenic strains, receiving identical input microbiota. The host's polymorphic mechanisms affect the gut microbiome, and both innate (anti-microbial peptides, complement, pentraxins, and enzymes affecting microbial survival) and adaptive (MHC-dependent and MHC-independent) pathways influence the microbiota. In our experiments, polymorphic mechanisms regulate only a limited number of microbial lineages (independently of their abundance). Our comparative analyses suggest that some microbes may benefit from the specific immune responses that they elicit.