The maternally inherited intracellular bacteria Wolbachia can manipulate host reproduction in various ways that foster frequency increases within and among host populations. Manipulations involving cytoplasmic incompatibility (CI), where matings between infected males and uninfected females produce non-viable embryos, are common in arthropods and produce a reproductive advantage for infected females. CI was associated with the spread of Wolbachia variant wRi in Californian populations of Drosophila simulans, which was interpreted as a bistable wave, in which local infection frequencies tend to increase only once the infection becomes sufficiently common to offset imperfect maternal transmission and infection costs. However, maternally inherited Wolbachia are expected to evolve towards mutualism, and they are known to increase host fitness by protecting against infectious microbes or increasing fecundity. We describe the sequential spread over approximately 20 years in natural populations of D. simulans on the east coast of Australia of two Wolbachia variants (wAu and wRi), only one of which causes significant CI, with wRi displacing wAu since 2004. Wolbachia and mtDNA frequency data and analyses suggest that these dynamics, as well as the earlier spread in California, are best understood as Fisherian waves of favourable variants, in which local spread tends to occur from arbitrarily low frequencies. We discuss implications for Wolbachia-host dynamics and coevolution and for applications of Wolbachia to disease control.