The acquisition of plasmids is often accompanied by high fitness costs such that compensatory evolution is required to allow plasmid survival. The mercury-resistance plasmid, pQBR55, drastically reduced the growth of its host, *Pseudomonas fluorescens* SBW25, immediately after acquisition, causing a small colony phenotype. We observed rapid restoration of the ancestral large colony morphology within just 48 hours of growth on agar plates, suggesting that compensatory mutations had occurred. Using genome sequencing we identified that restoration of the large colony phenotype was associated with chromosomal mutations in either an uncharacterised hypothetical 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. These data show that compensatory evolution can occur through three distinct mutational pathways and is fast enough to allow the survival of a plasmid despite it imposing very high fitness costs upon its host.