Parasites and hosts interact across both micro- and macroevolutionary scales where congruence among their phylogeographic and phylogenetic structures may be observed. Within southern Africa, the four-striped mouse genus, Rhabdomys, is parasitized by the ectoparasitic sucking louse, Polyplax arvicanthis. Molecular data recently suggested the presence of two cryptic species within P. arvicanthis that are sympatrically distributed across the distributions of four putative Rhabdomys species. We tested the hypotheses of phylogeographic congruence and cophylogeny among the two parasite lineages and the four host taxa, utilizing mitochondrial and nuclear sequence data. Despite the documented host-specificity of P. arvicanthis, limited phylogeographic correspondence and nonsignificant cophylogeny was observed. Instead, the parasite–host evolutionary history is characterized by limited codivergence and several duplication, sorting and host-switching events. Despite the elevated mutational rates found for P. arvicanthis, the spatial genetic structure was not more pronounced in the parasite lineages compared with the hosts. These findings may be partly attributed to larger effective population sizes of the parasite lineages, the vagility and social behaviour of Rhabdomys, and the lack of host-specificity observed in areas of host sympatry. Further, the patterns of genetic divergence within parasite and host lineages may also be largely attributed to historical biogeographic changes (expansion-contraction cycles). It is thus evident that the association between P. arvicanthis and Rhabdomys has been shaped by the synergistic effects of parasite traits, host-related factors and biogeography over evolutionary time.