Large conjugative plasmids are important drivers of bacterial evolution and contribute significantly to the dissemination of antibiotic resistance. Although plasmid borne multidrug resistance is recognized as one of the main challenges in modern medicine, the adaptive forces shaping the evolution of these plasmids within pathogenic hosts are poorly understood. Here we study plasmid-host adaptations following transfer of a 73 kb conjugative multidrug resistance plasmid to naïve clinical isolates of Klebsiella pneumoniae and Escherichia coli. We use experimental evolution, mathematical modelling and population sequencing to show that the long-term persistence and molecular integrity of the plasmid is highly influenced by multiple factors within a 25 kb plasmid region constituting a host-dependent burden. In the E. coli hosts investigated here, improved plasmid stability readily evolves via IS26 mediated deletions of costly regions from the plasmid backbone, effectively expanding the host-range of the plasmid. Although these adaptations were also beneficial to plasmid persistence in a naïve K. pneumoniae host, they were never observed in this species, indicating that differential evolvability can limit opportunities of plasmid adaptation. While insertion sequences are well known to supply plasmids with adaptive traits, our findings suggest that they also play an important role in plasmid evolution by maintaining the plasticity necessary to alleviate plasmid-host constrains. Further, the observed evolutionary strategy consistently followed by all evolved E. coli lineages exposes a trade-off between horizontal and vertical transmission that may ultimately limit the dissemination potential of clinical multidrug resistance plasmids in these hosts.