Phenetic and phylogenetic relationships in the Heterodoxus octoseriatus group of species were explored with data from 21 putative allozyme loci. The phenetic analyses and some of the cladistic analyses (maximum parsimony) were consistent with a phenetic analysis of morphological characters in that they indicated two main lines of evolution in the H. octoseriatus group. These culminated in two groups of species: (i) H. harrisoni, H. hughendensis, H. closei, H. maynesi, H. octoseriatus, H. lesouefi, H. briscoei and H. insulatus, and (ii) H. murrayi, H. insularis and H. orarius. The allozyme and morphological analyses, however, differed in the arrangement of species within the two main groups. Other cladistic analyses revealed the first group of lice, but not the second group. A hypothesis proposed for the evolution of the H. octoseriatus group involves widespread host-switching followed by the expansion of the geographic ranges of some lice at the expense of others. The evolution of host-parasite associations among rock-wallabies and lice from the H. octoseriatus group demonstrates how tangled the history of host-parasite associations may become.