Abstract Wolbachiae are obligate intracellular bacteria that infect arthropods and certain nematodes. Usually maternally inherited, they may provision nutrients to (mutualism) or alter sexual biology of (reproductive parasitism) their invertebrate hosts. We report the assembly of closed genomes for two novel wolbachiae, w CfeT and w CfeJ, found co-infecting cat fleas ( Ctenocephalides felis ) of the Elward Laboratory colony (Soquel, CA). w CfeT is basal to nearly all described Wolbachia supergroups, while w CfeJ is related to supergroups C, D and F. Both genomes contain laterally transferred genes that inform on the evolution of Wolbachia host associations. w CfeT carries the Biotin synthesis Operon of Obligate intracellular Microbes (BOOM); our analyses reveal five independent acquisitions of BOOM across the Wolbachia tree, indicating parallel evolution towards mutualism. Alternately, w CfeJ harbors a toxin-antidote operon analogous to the w Pip cinAB operon recently characterized as an inducer of cytoplasmic incompatibility (CI) in flies. w CfeJ cinB and immediate-5’ end genes are syntenic to large modular toxins encoded in CI-like operons of certain Wolbachia strains and Rickettsia species, signifying that CI toxins streamline by fission of larger toxins. Remarkably, the C . felis genome itself contains two CI-like antidote genes, divergent from wCfeJ cinA , revealing episodic reproductive parasitism in cat fleas and evidencing mobility of CI loci independent of WO-phage. Additional screening revealed predominant co-infection ( w CfeT/ w CfeJ) amongst C . felis colonies, though occasionally w CfeJ singly infects fleas in wild populations. Collectively, genomes of w CfeT, w CfeJ, and their cat flea host supply instances of lateral gene transfers that could drive transitions between parasitism and mutualism. Importance Many arthropod and certain nematode species are infected with wolbachiae which are intracellular bacteria well known for reproductive parasitism (RP). Like other RP strategies, Wolbachia -induced cytoplasmic incompatibility, CI, increases prevalence and frequency in host populations. Mutualism is another strategy employed by wolbachiae to maintain host infection, with some strains synthesizing and supplementing certain B vitamins (particularly biotin) to invertebrate hosts. Curiously, we discovered two novel Wolbachia strains that co-infect cat fleas ( Ctenocephalides felis ): w CfeT carries biotin synthesis genes, while w CfeJ carries a CI-inducing toxin-antidote operon. Our analyses of these genes highlight their mobility across the Wolbachia phylogeny and source to other intracellular bacteria. Remarkably, the C . felis genome also carries two CI-like antidote genes divergent from the w CfeJ antidote gene, indicating episodic RP in cat fleas. Collectively, w CfeT and w CfeJ inform on the rampant dissemination of diverse factors that mediate Wolbachia strategies for persisting in invertebrate host populations.