Livistona mariae is an endemic palm localized in arid central Australia. This species is separated by about 1000 km from its congener L. rigida, which grows distantly in the Roper River and Nicholson-Gregory River catchments in northern Australia. Such an isolated distribution of L. mariae has been assumed to have resulted from contraction of ancestral populations as Australia aridified from the Mid-Miocene (ca 15 Ma). To test this hypothesis at the population level, we examined the genetic relationships among 14 populations of L. mariae and L. rigida using eight nuclear microsatellite loci. Our population tree and Bayesian clustering revealed that these populations comprised two genetically distinct groups that did not correspond to the current classification at species rank, and L. mariae showed closest affinity with L. rigida from Roper River. Furthermore, coalescent divergence-time estimations suggested that the disjunction between the northern populations (within L. rigida) could have originated by intermittent colonization along an ancient river that has been drowned repeatedly by marine transgression. During that time, L. mariae populations could have been established by opportunistic immigrants from Roper River about 15 000 years ago, concurrently with the settlement of indigenous Australians in central Australia, who are thus plausible vectors. Thus, our results rule out the ancient relic hypothesis for the origin of L. mariae.