While theory suggests conditions under which mutualism may evolve from parasitism, few studies have observed this transition empirically. Previously, we evolved Escherichia coli and the filamentous bacteriophage M13 in 96-well microplates, an environment in which the ancestral phage increased the growth rate and yield of the ancestral bacteria. In the majority of populations, mutualism was maintained or even enhanced between phages and coevolving bacteria; however, these same phages evolved traits that harmed the ancestral E. coli genotype. Here, we set out to determine if mutualism could evolve from this new parasitic interaction. To do so, we chose six evolved phage populations from the original experiment and used them to establish new infections of the ancestral bacteria. After 20 passages, mutualism evolved in almost all replicates, with the remainder growing commensally. Many phage populations also evolved to benefit both their local, evolving bacteria and the ancestral bacteria, though these phages were less beneficial to their co-occurring hosts than phages that harm the ancestral bacteria. These results demonstrate the rapid recovery of mutualism from parasitism, and we discuss how our findings relate to the evolution of phages that enhance the virulence of bacterial pathogens.