Host–parasite coevolutionary histories can differ among multiple groups of parasites associated with the same group of hosts. For example, parasitic wing and body lice (Insecta: Phthiraptera) of New World pigeons and doves (Aves: Columbidae) differ in their cophylogenetic patterns, with body lice exhibiting higher phylogenetic congruence with their hosts than wing lice. In this study, we focus on the wing and body lice of Australian phabine pigeons and doves to determine whether the patterns in New World pigeons and doves are consistent with those of pigeons and doves from other regions. Using molecular sequence data for most phabine species and their lice, we estimated phylogenetic trees for all three groups (pigeons and doves, wing lice and body lice), and compared the phabine (host) tree with both parasite trees using multiple cophylogenetic methods. We found a pattern opposite to that found for New World pigeons and doves, with Australian wing lice showing congruence with their hosts, and body lice exhibiting a lack of congruence. There are no documented records of hippoboscid flies associated with Australian phabines, thus these lice may lack the opportunity to disperse among host species by attaching to hippoboscid flies (phoresis), which could explain these patterns. However, additional sampling for flies is needed to confirm this hypothesis. Large differences in body size among phabine pigeons and doves may also help to explain the congruence of the wing lice with their hosts. It may be more difficult for wing lice than body lice to switch among hosts that vary more dramatically in size. The results from this study highlight how host–parasite coevolutionary histories can vary by region, and how local factors can shape the relationship.