Wolbachia, one of the most widespread endosymbionts, is a target for biological control of mosquito-borne diseases (malaria and dengue virus), and antibiotic elimination of infectious filarial nematodes. We sequenced and analyzed the genome of a new Wolbachia strain (wPpe) in the plant-parasitic nematode Pratylenchus penetrans. Phylogenomic analyses placed wPpe as the earliest diverging Wolbachia, suggesting two evolutionary invasions into nematodes. The next branches comprised strains in sap-feeding insects, suggesting Wolbachia may have first evolved as a nutritional mutualist. Genome size, protein content, %GC, and repetitive DNA allied wPpe with mutualistic Wolbachia, whereas gene repertoire analyses placed it between parasite (A, B) and mutualist (C, D, F) groups. Conservation of iron metabolism genes across Wolbachia suggests iron homeostasis as a potential factor in its success. This study enhances our understanding of this globally pandemic endosymbiont, highlighting genetic patterns associated with host changes. Combined with future work on this strain, these genomic data could help provide potential new targets for plant-parasitic nematode control.