The Australian continent exhibits complex biogeographic patterns but studies of the impacts of Pleistocene climatic oscillation on the mesic environments of the Southern Hemisphere are limited. The koala (Phascolarctos cinereus), one of Australia's most iconic species, was historically widely distributed throughout much of eastern Australia but currently represents a complex conservation challenge. To better understand the challenges to koala genetic health, we assessed the phylogeographic history of the koala. Variation in the maternally inherited mitochondrial DNA (mtDNA) Control Region (CR) was examined in 662 koalas sampled throughout their distribution. In addition, koala CR haplotypes accessioned to Genbank were evaluated and consolidated. A total of 53 unique CR haplotypes have been isolated from koalas to date (including 15 haplotypes novel to this study). The relationships among koala CR haplotypes were indicative of a single Evolutionary Significant Unit and do not support the recognition of subspecies, but were separated into four weakly differentiated lineages which correspond to three geographic clusters: a central lineage, a southern lineage and two northern lineages co-occurring north of Brisbane. The three geographic clusters were separated by known Pleistocene biogeographic barriers: the Brisbane River Valley and Clarence River Valley, although there was evidence of mixing amongst clusters. While there is evidence for historical connectivity, current koala populations exhibit greater structure, suggesting habitat fragmentation may have restricted female-mediated gene flow. Since mtDNA data informs conservation planning, we provide a summary of existing CR haplotypes, standardise nomenclature and make recommendations for future studies to harmonise existing datasets. This holistic approach is critical to ensuring management is effective and small scale local population studies can be integrated into a wider species context.