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, CfeT and CfeJ, found co-infecting cat fleas () of the Elward Laboratory colony (Soquel, CA, USA). CfeT is basal to nearly all described supergroups, while CfeJ is related to supergroups C, D and F. Both genomes contain laterally transferred genes that inform on the evolution of host associations. CfeT carries the Biotin synthesis Operon of Obligate intracellular Microbes (BOOM); our analyses reveal five independent acquisitions of BOOM across the tree, indicating parallel evolution towards mutualism. Alternately, CfeJ harbors a toxin-antidote operon analogous to the Pip operon recently characterized as an inducer of cytoplasmic incompatibility (CI) in flies. CfeJ and three adjacent genes are collectively similar to large modular toxins encoded in CI-like operons of certain strains and species, signifying that CI toxins streamline by fission of large modular toxins. Remarkably, the . genome itself contains two CI-like antidote genes, divergent from CfeJ , revealing episodic reproductive parasitism in cat fleas and evidencing mobility of CI loci independent of WO-phage. Additional screening revealed predominant co-infection (CfeT/CfeJ) amongst . colonies, though fleas in wild populations mostly harbor CfeT alone. Collectively, genomes of CfeT, CfeJ, and their cat flea host supply instances of lateral gene transfers that could drive transitions between parasitism and mutualism.