Species interactions can shift along the parasitism-mutualism continuum. However, the consequences of these transitions for coevolutionary interactions remain unclear. We experimentally coevolved a novel species interaction between Caenorhabditis elegans hosts and a mildly parasitic bacterium, Enterococcus faecalis, with host-protective properties against virulent Staphylococcus aureus. Coinfections drove the evolutionary transition of the C.elegans-E. faecalis relationship towards a reciprocally beneficial interaction. As E. faecalis evolved to protect nematodes against S. aureus infection, hosts adapted by accommodating greater numbers of protective bacteria. The mutualism was strongest in pairings of contemporary coevolved populations. To generally assess the conditions under which these defensive mutualisms can arise and coevolve, we analysed a model which showed that they are favoured when mild parasites confer an intermediate level of protection. Our results reveal that coevolution can shape the transition of animal-parasite interactions towards defensive symbioses in response to co-infections.