Many, but not all, parasitic filarial nematodes (Onchocercidae) carry intracellular, maternally transmitted, alphaproteobacterial Wolbachia symbionts. The association between filarial nematodes and Wolbachia is often portrayed as mutualist, where the nematode is reliant on Wolbachia for an essential but unknown service. Wolbachia are targets for antifilarial chemotherapeutic interventions for human disease. Wolbachia of Onchocercidae derive from four of the major supergroups (C, D, F, and J) defined within the genus. We explored the evolutionary history of the filarial nematode-Wolbachia symbiosis in 22 nematode species, 16 of which have current Wolbachia infections, by screening the nematode nuclear genome sequences for nuclear Wolbachia transfers, fragments of the Wolbachia genome that have been inserted into the nuclear genome. We identified Wolbachia insertions in 5 of the 6 species that have no current Wolbachia infection, showing they have previously had and have now lost Wolbachia infections. In currently infected species, we found a diversity of origins of the insertions, including many cases where they derived from a different supergroup to the current live infection. Mapping the origins of the insertions onto the filarial nematode phylogeny we derive a complex model of evolution of Wolbachia symbiosis. The history of association between Wolbachia and onchocercid nematodes includes not only cospeciation, as would be expected from a mutualist symbiosis, but also loss (in the 5 Wolbachia-free species), frequent symbiont replacement, and dual infection. This dynamic pattern is challenging to models that assume host–symbiont mutualism.