Background: Long-term persistent symbiotic associations may result in co-speciation and can be inferred if species trees of hosts and symbionts are congruent in topology and divergence times. Co-speciation has been seen to occur relatively frequently in obligate associations, but is less common in parasitic or facultative ones, mainly due to the difference in horizontal transmission rates. The long-term vertical inheritance and close host association of obligate endosymbionts also generally result in smaller genomes than in facultative endosymbionts. Here, we investigate co-speciation and genome reduction using highly similar strains of the endosymbiont Wolbachia infecting Drosophila species from the willistoni and saltans groups, where only one strain, wPau, infecting D. paulistorum, is obligate. Results: We sequenced the Wolbachia genomes from five species of the willistoni and saltans groups and constructed phylogenies. Topological congruence was found between these Wolbachia strains and the nuclear DNA of their hosts, except for wPau and D. paulistorum, but full topological congruence was observed between Wolbachia and the host mitochondrial DNA. However, assuming temporal congruence, we estimated extremely low evolutionary rates in Wolbachia of 10-10-10-11 changes/site/year. Additionally, the obligate wPau strain was found to have a larger genome than closely related facultative strains, mainly due to an ongoing expansion of an IS4 element. Furthermore, wPau has lost a large proportion of its prophage WO genes, but the cif genes, known to be involved in the CI phenotype, are intact. Finally, nine of the eleven genes from the prophage WO-associated Undecim cluster are uniquely duplicated. Conclusions: The congruent topologies between Wolbachia and their willistoni and saltans group hosts indicate co-speciation. However, the high similarity between Wolbachia strains, which results in low mutation rate estimates, challenges this interpretation. Contrary to the expectations of the genome reduction theory, we observed an increase in genome size in the obligate wPau strain, potentially driven by a decreased population size. Finally, the duplication of the Undecim cluster despite a major loss of other prophage-associated genes suggests that the genes in the Undecim cluster are under strong selection and potentially play a role in the obligate association between wPau and their D. paulistorum hosts.