Little is known about the range of hosts in which broad-host-range (BHR) plasmids can persist in the absence of selection for plasmid-encoded traits, and whether this "long-term host range" can evolve over time. Previously, the BHR multidrug resistance plasmid pB10 was shown to be highly unstable in Stenotrophomonas maltophilia P21 and Pseudomonas putida H2. To investigate whether this plasmid can adapt to such unfavorable hosts, we performed evolution experiments wherein pB10 was maintained in strain P21, strain H2, and alternatingly in P21 and H2. Plasmids that evolved in P21 and in both hosts showed increased stability and decreased cost in ancestral host P21. However, the latter group showed higher variability in stability patterns, suggesting that regular switching between distinct hosts hampered adaptive plasmid evolution. The plasmids evolved in P21 were also equally or more stable in other hosts compared to pB10, which suggested true host-range expansion. The complete genome sequences of four evolved plasmids with improved stability showed only one or two genetic changes. The stability of plasmids evolved in H2 improved only in their coevolved hosts, not in the ancestral host. Thus a BHR plasmid can adapt to an unfavorable host and thereby expand its long-term host range.