Background. How host-symbiont interactions coevolve between mutualism and parasitism depends on the ecology of the system and on the genetic and physiological constraints of the organisms involved. Theory often predicts that greater reliance on horizontal transmission favors increased costs of infection and may result in more virulent parasites or less beneficial mutualists. We set out to understand transitions between parasitism and mutualism by evolving the filamentous bacteriophage M13 and its host Escherichia coli. Results. The effect of phage M13 on bacterial fitness depends on the growth environment, and initial assays revealed that infected bacteria reproduce faster and to higher density than uninfected bacteria in 96-well microplates. These data suggested that M13 is, in fact, a facultative mutualist of E. coli. We then allowed E. coli and M13 to evolve in replicated environments, which varied in the relative opportunity for horizontal and vertical transmission of phage in order to assess the evolutionary stability of this mutualism. After 20 experimental passages, infected bacteria from treatments with both vertical and horizontal transmission of phage had evolved the fastest growth rates. At the same time, phage from these treatments no longer benefited the ancestral bacteria. Conclusions. These data suggest a positive correlation between the positive effects of M13 on E. coli hosts from the same culture and the negative effects of the same phage toward the ancestral bacterial genotype. The results also expose flaws in applying concepts from the virulence-transmission tradeoff hypothesis to mutualism evolution. We discuss the data in the context of more recent theory on how horizontal transmission affects mutualisms and explore how these effects influence phages encoding virulence factors in pathogenic bacteria.