Ecological and evolutionary theories predict that parasitism and mutualism are not fixed endpoints of the symbiotic spectrum. Rather, parasitism and mutualism may be host or environment dependent, induced by the same genetic machinery, and shifted due to selection. These models presume the existence of genetic or environmental variation that can spur incipient changes in symbiotic lifestyle. However, for obligate intracellular bacteria whose genomes are highly reduced, studies specify that discrete symbiotic associations can be evolutionarily stable for hundreds of millions of years. Wolbachia is an inherited obligate, intracellular infection of invertebrates containing taxa that act broadly as both parasites in arthropods and mutualists in certain roundworms. Here, we analyze the ancestry of mutualism and parasitism in Wolbachia and the evolutionary trajectory of this variation in symbiotic lifestyle with a comprehensive, phylogenomic analysis. Contrary to previous claims, we show unequivocally that the transition in lifestyle cannot be reconstructed with current methods due to long-branch attraction (LBA) artifacts of the distant Anaplasma and Ehrlichia outgroups. Despite the use of 1) site-heterogenous phylogenomic methods that can overcome systematic error, 2) a taxonomically rich set of taxa, and 3) statistical assessments of the genes, tree topologies, and models of evolution, we conclude that the LBA artifact is serious enough to afflict past and recent claims including the root lies in the middle of the Wolbachia mutualists and parasites. We show that different inference methods yield different results and high bootstrap support did not equal phylogenetic accuracy. Recombination was rare among this taxonomically diverse data set, indicating that elevated levels of recombination in Wolbachia are restricted to specific coinfecting groups. In conclusion, we attribute the inability to root the tree to rate heterogeneity between the ingroup and outgroup. Site-heterogenous models of evolution did improve the placement of aberrant taxa in the ingroup phylogeny. Finally, in the unrooted topology, the distribution of parasitism and mutualism across the tree suggests that at least two interphylum transfers shaped the origins of nematode mutualism and arthropod parasitism. We suggest that the ancestry of mutualism and parasitism is not resolvable without more suitable outgroups or complete genome sequences from all Wolbachia supergroups.