Many animal and plant species harbour microbes in their microbiota that protect them from parasite infection. These ‘protective microbes’ can be a significant component of host defence. Using experimental evolution of a novel, tripartite interaction, my group has demonstrated that a costly bacterium living in worms can rapidly evolve to defend their animal hosts against infection by virulent parasites, thus crossing the parasitism-mutualism continuum. We also show that these protective microbes can drive major changes in host tolerance, parasite virulence and coevolutionary dynamics. Our results indicate that the host microbiome is important in shaping infection outcomes, now and over evolutionary time.