There has been a proliferation of studies demonstrating an organism’s health is influenced by its microbiota. However, factors influencing beneficial microbe colonization and the evolution of these relationships remain understudied relative to host-pathogen interactions. Vertically transmitted beneficial microbes are predicted to show high levels of specificity in colonization, including genotype matching, which may transpire through coevolution. We investigate how host and bacterial genotypes influence colonization of a core coevolved microbiota member in bumble bees. The hindgut colonizing Snodgrassella alvi confers direct benefits, but, as an early colonizer, also facilitates the further development of a healthy microbiota. Due to predominantly vertical transmission promoting tight evolution between colonization factors of bacteria and host lineages, we predict that genotype-by-genotype interactions will determine successful colonization. Germ-free adult bees from seven bumble bee colonies (host genotypic units) were inoculated with one of six genetically distinct strains of S. alvi. Subsequent colonization within host-genotype and microbe-genotype combinations ranged from zero to one hundred percent, and an interaction between host and microbe genotypes determined colonization success. This novel finding of a genotype-by-genotype interaction determining colonization in an animal host-beneficial microbe system has implications for the ecological and evolutionary dynamics of host and microbe, including associated host-fitness benefits.