The Australian koala is an iconic marsupial with highly specific dietary requirements distributed across heterogeneous environments, over a large geographic range. The distribution and genetic structure of koala populations has been heavily influenced by human actions, specifically habitat modification, hunting and translocation of koalas. There is currently limited information on population diversity and gene flow at a species-wide scale, or with consideration to the potential impacts of local adaptation. Using species-wide sampling across heterogeneous environments, and high-density genome-wide markers (SNPs and PAVs), we show that most koala populations display levels of diversity comparable to other outbred species, except for those populations impacted by population reductions. Genetic clustering analysis and phylogenetic reconstruction reveals a lack of support for current taxonomic classification of three koala subspecies, with only a single evolutionary significant unit supported. Furthermore, ~70% of genetic variance is accounted for at the individual level. The Sydney Basin region is highlighted as a unique reservoir of genetic diversity, having higher diversity levels (i.e., Blue Mountains region; AvHecorr=0.20, PL% = 68.6). Broad-scale population differentiation is primarily driven by an isolation by distance genetic structure model (49% of genetic variance), with clinal local adaptation corresponding to habitat bioregions. Signatures of selection were detected between bioregions, with no single region returning evidence of strong selection. The results of this study show that although the koala is widely considered to be a dietary-specialist species, this apparent specialisation has not limited the koala’s ability to maintain gene flow and adapt across divergent environments as long as the required food source is available.