Insects with nutritionally limited diets often harbor bacterial endosymbionts that supplement their nutritional requirements. However, not all interactions between bacteria and insects are mutually beneficial. Wolbachia is a genus of bacteria that frequently causes cytoplasmic incompatibility and other reproductive parasitic effects on many of its arthropod hosts. In nematodes and some insects, however, Wolbachia is a nutritional mutualist. A lineage of Wolbachia closely related to mutualist strains has previously been identified in parasitic lice, including the louse genus Penenirmus (Ischnocera), which specializes in feeding on feathers. In this study, we used genome-resolved metagenomics to examine the diversity of Wolbachia across the genus Penenirmus, with a focus on evidence of long term associations with their hosts, which could indicate a mutualistic relationship. Phylogenomic analysis of over 100 genes from Wolbachia provided a well-resolved phylogeny of this bacterial genus. Across diverse species of the louse genus Penenirmus, genome-resolved metagenomic assemblies of Wolbachia from these insects revealed the presence of three different supergroups (B, F, and V). Supergroup V had not previously been known from lice. Cophylogenetic analysis revealed significant congruence between the Wolbachia and louse trees, although some branches showed incongruence. The Wolbachia in Penenirmus species from supergroups F and B showed evidence of potential mutualism by having long branches, cophylogenetic congruence with their louse hosts, and comparatively smaller genome sizes. Long branch attraction may be affecting the phylogenetic position of two lineages of Wolbachia, but the relative position of all other samples was comparatively stable.