Plasmids drive genomic diversity in bacteria via horizontal gene transfer [1 and 2]; nevertheless, explaining their survival in bacterial populations is challenging . Theory predicts that irrespective of their net fitness effects, plasmids should be lost: when parasitic (costs outweigh benefits), plasmids should decline due to purifying selection [4, 5 and 6], yet under mutualism (benefits outweigh costs), selection favors the capture of beneficial accessory genes by the chromosome and loss of the costly plasmid backbone . While compensatory evolution can enhance plasmid stability within populations [7, 8, 9, 10, 11, 12, 13, 14 and 15], the propensity for this to occur across the parasitism-mutualism continuum is unknown. We experimentally evolved Pseudomonas fluorescens and its mercury resistance mega-plasmid, pQBR103 [ 16], across an environment-mediated parasitism-mutualism continuum. Compensatory evolution stabilized plasmids by rapidly ameliorating the cost of plasmid carriage in all environments. Genomic analysis revealed that, in both parasitic and mutualistic treatments, evolution repeatedly targeted the gacA/gacS bacterial two-component global regulatory system while leaving the plasmid sequence intact. Deletion of either gacA or gacS was sufficient to completely ameliorate the cost of plasmid carriage. Mutation of gacA/gacS downregulated the expression of ∼17% of chromosomal and plasmid genes and appears to have relieved the translational demand imposed by the plasmid. Chromosomal capture of mercury resistance accompanied by plasmid loss occurred throughout the experiment but very rarely invaded to high frequency, suggesting that rapid compensatory evolution can limit this process. Compensatory evolution can explain the widespread occurrence of plasmids and allows bacteria to retain horizontally acquired plasmids even in environments where their accessory genes are not immediately useful.