Wolbachia are maternally inherited bacteria that commonly spread through host populations by causing cytoplasmic incompatibility, often expressed as reduced egg hatch when uninfected females mate with infected males. Infected females are frequently less fecund as a consequence of Wolbachia infection. However, theory predicts that because of maternal transmission, these "parasites" will tend to evolve towards a more mutualistic association with their hosts. Drosophila simulans in California provided the classic case of a Wolbachia infection spreading in nature. Cytoplasmic incompatibility allowed the infection to spread through individual populations within a few years and from southern to northern California (more than 700 km) within a decade, despite reducing the fecundity of infected females by 15%-20% under laboratory conditions. Here we show that the Wolbachia in California D. simulans have changed over the last 20 y so that infected females now exhibit an average 10% fecundity advantage over uninfected females in the laboratory. Our data suggest smaller but qualitatively similar changes in relative fecundity in nature and demonstrate that fecundity-increasing Wolbachia variants are currently polymorphic in natural populations.