The heath mouse (Pseudomys shortridgei) is a locally rare species; it was considered extinct in Western Australia until its rediscovery 20 years ago. It is not often detected in faunal surveys and is confined to two ecologically distinct habitats on either side of the Australian continent. An important and immediate conservation question has been to determine the genetic diversity within each of its current habitats and to determine the differences between the geographically separate populations. Measures of genetic differentiation amongst P. shortridgei populations in their eastern (Victoria) and western (Western Australia) distribution were estimated using nuclear (microsatellite loci) and partial sequence of mitochondrial DNA (427 bp Cytochrome b gene and 637 bp of the D-loop). Both markers identified differences between the east- and west-coast populations. MtDNA data showed significant divergence between populations with monophyly within them, and nuclear loci investigated also showed two clear genetic clusters based on Bayesian inference. As a result of these findings, we suggest that the heath mouse comprises two highly divergent (but genetically diverse) lineages and the aridity of the Nullarbor Plain has clearly been a barrier for dispersal since the early Pleistocene (~1.43 million years ago). The populations either side of the Nullarbor Plain are genetically differentiated and should be defined as separate Evolutionary Significant Units (ESUs).