Associations between bacteria and their accessory elements (viruses, plasmids and transposons) range from antagonistic to mutualistic. A number of previous studies have demonstrated that plasmid carriage reduces bacterial fitness in the absence of selection for specific functions such as antibiotic resistance. Many studies have demonstrated increased fitness of evolving microbial populations in laboratory environments, but we are aware of only one study in which fitness gains were partitioned between a plasmid and its host. Here, we examine the evolution of an association between a plasmid and its bacterial host. Carriage of the non-conjugative plasmid pACYC184 initially reduced the fitness of Escherichia coli B in the absence of antibiotic. We then cultured plasmid-bearing bacteria for 500 generations in the presence of antibiotic. The fitness of each combination of host and plasmid, with and without the culture history, was determined by competing it against a baseline strain. The results indicate adaptation by the host genome, but no plasmid adaptation. We also competed the evolved host, transformed with the baseline plasmid, against its isogenic plasmid-free counterpart. The plasmid now increased the fitness of its host.