Conjugative plasmids are extra-chromosomal DNA elements that are capable of horizontal transmission and are found in many natural isolated bacteria. Although plasmids may carry beneficial genes to their bacterial host, they may also cause a fitness cost. In this work, we studied the evolution of the R1 plasmid and we found that, in spite of the R1 plasmid conferring an initial cost to its host, after 420 generations the cost disappeared in all five independent evolution experiments. In fact, in two of these five experiments evolved conjugative plasmids actually conferred a fitness advantage to their hosts. Furthermore, the relative fitness of the ancestral clone bearing one of the evolved plasmids is significantly higher than both the plasmid-free ancestral cells and the evolved cells carrying the evolved plasmid. Given that the R1 plasmid may spread among different species of enterobacteria, we wondered what the effect of the evolved plasmid would be inside Salmonella enterica cells. We found that the evolved plasmid is also able to dramatically increase the relative fitness of these cells. Our results suggest that even if general usage of antibiotics is halted, conjugative plasmids that have been selected with antibiotics in previous years can still persist among bacterial populations or even invade new strains.