Wolbachia are vertically transmitted bacteria known from arthropods and nematode worms, which are maintained in host populations because they either physiologically benefit infected individuals or parasitically manipulate their reproduction. The different manipulation phenotypes are scattered across the Wolbachia phylogeny, suggesting that there have been multiple evolutions of similar phenotypes. This conclusion relies on the assumption of an absence of recombination between bacterial strains, so that the gene used to reconstruct the phylogeny reflects the evolutionary history of the genes involved in the trait. We tested for recombination by reconstructing the phylogeny of two Wolbachia genes from seven B-subdivision strains. The two genes produced mutually incompatible topologies, indicating that these lineages are subject to genetic recombination. This means that many evolutionary patterns inferred from Wolbachia phylogenies must be re-evaluated. Furthermore, recombination may be an important feature both in the evolution of the manipulation phenotypes and avoidance of Müller's ratchet. Finally, we discuss the implications of recombination for attempts to genetically engineer Wolbachia for use in the control of crop pests and human pathogens.