To exemplify autoimmune-associated genetic influence on the colonization of bacteria frequently used in probiotics, microbial composition of stool from 1326 one-year-old infants was analyzed in a prospective general-population cohort, All Babies In Southeast Sweden (ABIS). We show that an individual's HLA haplotype composition has a significant impact on which common Bifidobacterium strains thrive in colonizing the gut. The effect HLA has on the gut microbiome can be more clearly observed when considered in terms of allelic dosage. HLA DR1-DQ5 showed the most significant and most prominent effect on increased Bifidobacterium relative abundance. Therefore, HLA DR1-DQ5 is proposed to act as a protective haplotype in many individuals. Protection-associated HLA haplotypes are more likely to influence the promotion of specific bifidobacteria. In addition, strain-level differences are correlated with colonization proficiency in the gut depending on HLA haplotype makeup. These results demonstrate that HLA genetics should be considered when designing effective probiotics, particularly for those at high genetic risk for autoimmune diseases.