We addressed phylogenetic relationships among species of Planipapillus, a clade of oviparous onychophorans from southeastern mainland Australia, to create a framework for understanding the evolution of the modified male head papillae used in mating in this clade. We sequenced fragments of two mitochondrial genes, COI and 12S rRNA, and a nuclear intron from the fushi tarazu gene, for individuals from 14 putative species of Planipapillus and six outgroups. We analyzed these data under both parsimony and likelihood criteria, incorporating heterogeneous parameter fitting guided by likelihood ratio tests. These analyses result in strong, congruent support for many clades. We infer multiple independent origins of spikes in Planipapillus male head structures.