The coevolution of interacting species can lead to codependent mutualists. Little is known about the effect of selection on partners within verses apart from the association. Here, we determined the effect of selection on bacteria (Xenorhabdus nematophila) both within and apart from its mutualistic partner (a nematode, Steinernema carpocapsae). In nature, the two species cooperatively infect and kill arthropods. We passaged the bacteria either together with (M+), or isolated from (M−), nematodes under two different selection regimes: random selection (S−) and selection for increased virulence against arthropod hosts (S+). We found that the isolated bacteria evolved greater virulence under selection for greater virulence (M−S+) than under random selection (M−S−). In addition, the response to selection in the isolated bacteria (M−S+) caused a breakdown of the mutualism following reintroduction to the nematode. Finally, selection for greater virulence did not alter the evolutionary trajectories of bacteria passaged within the mutualism (M+S+ = M+S−), indicating that selection for the maintenance of the mutualism was stronger than selection for increased virulence. The results show that selection on isolated mutualists can rapidly breakdown beneficial interactions between species, but that selection within a mutualism can supersede external selection, potentially generating codependence over time.