Microbes can defend their host against virulent infections, but direct evidence for the adaptive origin of microbe-mediated protection is lacking. Using experimental evolution of a novel, tripartite interaction, we demonstrate that mildly pathogenic bacteria (Enterococcus faecalis) living in worms (Caenorhabditis elegans) rapidly evolved to defend their animal hosts against infection by a more virulent pathogen (Staphylococcus aureus), crossing the parasitism-mutualism continuum. Host protection evolved in all six, independently selected populations in response to within-host bacterial interactions and without direct selection for host health. Microbe-mediated protection was also effective against a broad spectrum of pathogenic S. aureus isolates. Genomic analysis implied that the mechanistic basis for E. faecalis-mediated protection was through increased production of antimicrobial superoxide, which was confirmed by biochemical assays. Our results indicate that microbes living within a host may make the evolutionary transition to mutualism in response to pathogen attack, and that microbiome evolution warrants consideration as a driver of infection outcome.