The mitochondrial genomes (mitogenomes) of bilaterian animals are highly conserved structures that usually consist of a single circular chromosome. However, several species of parasitic lice (Insecta: Phthiraptera) possess fragmented mitogenomes, where the mitochondrial genes are present on separate, circular chromosomes. Nevertheless, the extent, causes, and consequences of this structural variation remain poorly understood. Here, we combined new and existing data to better understand the evolution of mitogenome fragmentation in major groups of parasitic lice. We found strong evidence that fragmented mitogenomes evolved many times within parasitic lice and that the level of fragmentation is highly variable, including examples of heteroplasmic arrangements. We also found a significant association between mitochondrial fragmentation and signatures of relaxed selection. Mitochondrial fragmentation was also associated with changes to a lower AT%, possibly due to differences in mutation biases. Together, our results provide a significant advance in understanding the process of mitogenome fragmentation and provide an important perspective on mitochondrial evolution in eukaryotes.