Horizontal gene transfer mediated by broad-host-range plasmids is an important mechanism of antibiotic resistance spread. While not all bacteria maintain plasmids equally well, plasmid persistence can improve over time, yet no general evolutionary mechanisms have emerged. Our goal was to identify these mechanisms, and to assess if adaptation to one plasmid affects the permissiveness to others. We experimentally evolved Pseudomonas sp. H2 containing multi-drug resistance plasmid RP4, determined plasmid persistence and cost using a joint experimental-modeling approach, resequenced evolved clones, and reconstructed key mutations. Plasmid persistence improved in fewer than 600 generations because the fitness cost turned into a benefit. Improved retention of naive plasmids indicated that the host evolved towards increased plasmid permissiveness. Key chromosomal mutations affected two accessory helicases and the RNA polymerase β-subunit. Our and other findings suggest that poor plasmid persistence can be caused by a high cost involving helicase-plasmid interactions that can be rapidly ameliorated.