Long-term relationships between hosts and their bacterial endosymbionts can result in co-speciation. For obligate mutualistic associations, this occurs relatively frequently, but it is less common in parasitic or facultative relationships. Here, we have sequenced genomes of several very closely related Wolbachia strains, infecting fruit flies of the willistoni and saltans groups of Neotropical Drosophila, of which only one, the wPau strain infecting D. paulistorum, is obligate for its host. Using these genomes, we constructed phylogenies and found congruence between Wolbachia and their hosts, except for wPau and D. paulistorum, indicating mainly co-speciation between Wolbachia and willistoni and saltans group flies. However, the high similarity between Wolbachia strains implies low evolutionary rates and challenges the interpretation of our results as co-speciation. Additionally, contrary to the expectations of the genome reduction theory, we observed a genome size increase in the obligate wPau strain, which is due to an ongoing expansion of an IS4 element. Finally, although wPau has lost a large proportion of prophage WO genes, the cif genes are intact and nine genes from the WO-associated Undecim cluster are uniquely duplicated, suggesting they are under strong selection and potentially play a role in the obligate association.