The acquisition of plasmids is often accompanied by fitness costs such that compensatory evolution is required to allow plasmid survival, but it is unclear whether compensatory evolution can be extensive or rapid enough to maintain plasmids when they are very costly. The mercury-resistance plasmid pQBR55 drastically reduced the growth of its host, Pseudomonas fluorescens SBW25, immediately after acquisition, causing a small colony phenotype. However, within 48 h of growth on agar plates we observed restoration of the ancestral large colony morphology, suggesting that compensatory mutations had occurred. Relative fitness of these evolved strains, in lab media and in soil microcosms, varied between replicates, indicating different mutational mechanisms. Using genome sequencing we identified that restoration was associated with chromosomal mutations in either a hypothetical DNA-binding protein PFLU4242, RNA polymerase or the GacA/S two-component system. Targeted deletions in PFLU4242, gacA or gacS recapitulated the ameliorated phenotype upon plasmid acquisition, indicating three distinct mutational pathways to compensation. Our data shows that plasmid compensatory evolution is fast enough to allow survival of a plasmid despite it imposing very high fitness costs upon its host, and indeed may regularly occur during the process of isolating and selecting individual plasmid-containing clones.