Maternally transmitted Wolbachia bacteria infect about half of all insect species. Many Wolbachia cause cytoplasmic incompatibility (CI) and reduced egg hatch when uninfected females mate with infected males. Although CI produces a frequency-dependent fitness advantage that leads to high equilibrium Wolbachia frequencies, it does not aid Wolbachia spread from low frequencies. Indeed, the fitness advantages that produce initial Wolbachia spread and maintain non-CI Wolbachia remain elusive. wMau Wolbachia infecting Drosophila mauritiana do not cause CI, despite being very similar to CI-causing wNo from Drosophila simulans (0.068% sequence divergence over 682,494 bp), suggesting recent CI loss. Using draft wMau genomes, we identify a deletion in a CI-associated gene, consistent with theory predicting that selection within host lineages does not act to increase or maintain CI. In the laboratory, wMau shows near-perfect maternal transmission; but we find no significant effect on host fecundity, in contrast to published data. Intermediate wMau frequencies on the island of Mauritius are consistent with a balance between unidentified small, positive fitness effects and imperfect maternal transmission. Our phylogenomic analyses suggest that group-B Wolbachia, including wMau and wPip, diverged from group-A Wolbachia, such as wMel and wRi, 6-46 million years ago, more recently than previously estimated.