Mesic southeastern Australia represents the continent's ancestral biome and is highly biodiverse, yet its phylogeographic history remains poorly understood. Here, we examine mitochondrial DNA (mtDNA) control region and microsatellite diversity in the brush-tailed rock-wallaby (Petrogale penicillata; n = 279 from 31 sites), to assess historic evolutionary and biogeographic processes in southeastern Australia. Our results (mtDNA, microsatellites) confirmed three geographically discrete and genetically divergent lineages within brush-tailed rock-wallabies, whose divergence appears to date to the mid-Pleistocene. These three lineages had been hypothesized previously but data were limited. While the Northern and Central lineages were separated by a known biogeographic barrier (Hunter Valley), the boundary between the Central and Southern lineages was not. We propose that during particularly cool glacial cycles, the high peaks of the Great Dividing Range and the narrow adjacent coastal plain resulted in a more significant north-south barrier for mesic taxa in southeastern Australia than has been previously appreciated. Similarly, located phylogeographic breaks in codistributed species highlight the importance of these regions in shaping the distribution of biodiversity in southeastern Australia and suggest the existence of three major refuge areas during the Pleistocene. Substructuring within the northern lineage also suggests the occurrence of multiple local refugia during some glacial cycles. Within the three major lineages, most brush-tailed rock-wallaby populations were locally highly structured, indicating limited dispersal by both sexes. The three identified lineages represent evolutionarily significant units and should be managed to maximize the retention of genetic diversity within this threatened species.