Halfordia F.Muell is a genus of rainforest trees or shrubs native to New Guinea, New Britain, New Caledonia, Vanuatu and eastern Australia. There is debate about the number of species that should be recognised in the genus. Four species have been named, but authors have commonly recognised only two species, and some recent treatments accept just one widespread species with a broad ecological range. We sequenced two nrDNA markers (ITS and ETS) and two cpDNA markers (rbcL and trnL–trnF) from samples across the range of Halfordia in Australia and New Caledonia. Three allopatric nrDNA groups were resolved: one from southeast Queensland and northern New South Wales (Group A); one from the Wet Tropics region of North Queensland (Group B); and one from the Cape York region of North Queensland, Torres Strait and New Caledonia (Group C). These groups were also partly differentiated by more slowly evolving cpDNA markers; the exception was one widespread haplotype in Australia (presumed ancestral). The nrDNA groups support recognition of three previously described species: H. leichhardtii (Group A), H. scleroxyla (Group B) and H. kendack (Group C). Divergences among eastern Australia populations are best explained by vicariance and correlate with geographic breaks documented for other taxa (ranging in estimated ages from the mid-late Miocene to the Pleistocene). The broad distribution of Group C, from Cape York to New Caledonia, with less genetic divergence, arguably reflects recent range expansion into New Caledonia involving bird dispersal of fleshy fruits.