Wolbachia, endosymbiotic bacteria of the order Rickettsiales, are widespread in arthropods but also present in nematodes. In arthropods, A and B supergroup Wolbachia are generally associated with distortion of host reproduction. In filarial nematodes, including some human parasites, multiple lines of experimental evidence indicate that C and D supergroup Wolbachia are essential for the survival of the host, and here the symbiotic relationship is considered mutualistic. The origin of this mutualistic endosymbiosis is of interest for both basic and applied reasons: How does a parasite become a mutualist? Could intervention in the mutualism aid in treatment of human disease? Correct rooting and high-quality resolution of Wolbachia relationships are required to resolve this question. However, because of the large genetic distance between Wolbachia and the nearest outgroups, and the limited number of genomes so far available for large-scale analyses, current phylogenies do not provide robust answers. We therefore sequenced the genome of the D supergroup Wolbachia endosymbiont of Litomosoides sigmodontis, revisited the selection of loci for phylogenomic analyses, and performed a phylogenomic analysis including available complete genomes (from isolates in supergroups A, B, C, and D). Using 90 orthologous genes with reliable phylogenetic signals, we obtained a robust phylogenetic reconstruction, including a highly supported root to the Wolbachia phylogeny between a (A + B) clade and a (C + D) clade. Although we currently lack data from several Wolbachia supergroups, notably F, our analysis supports a model wherein the putatively mutualist endosymbiotic relationship between Wolbachia and nematodes originated from a single transition event.