The koala's Phascolarctos cinereus distribution is currently restricted to eastern and south-eastern Australia. However, fossil records dating from 70 ± 4 ka (ka = 103 yr) from south-western Australia and the Nullarbor Plain are evidence of subpopulation extinctions in the southwest at least after the Last Interglacial (~128-116 ka). We hypothesize that koala sub-population extinctions resulted from the eastward retraction of the koala's main browse species in response to unsuitable climatic conditions. We further posit a general reduction in the distribution of main koala-browse trees in the near future in response climate change. We modelled 60 koala-browse species and constructed a set of correlative species distribution models for five time periods: Last Interglacial (~128-116 ka), Last Glacial Maximum (~23-19 ka), Mid-Holocene (~7-5 ka), present (interpolations of observed data, representative of 1960-1990), and 2070. We based our projections on five hindcasts and one forecast of climatic variables extracted from WorldClim based on two general circulation models (considering the most pessimistic scenario of high greenhouse-gas emissions) and topsoil clay fraction. We used 17 dates of koala fossil specimens identified as reliable from 70 (± 4) to 535 (± 49) ka, with the last appearance of koalas at 70 ka in the southwest. The main simulated koala-browse species were at their greatest modelled extent of suitability during the Last Glacial Maximum, with the greatest loss of koala habitat occurring between the Mid-Holocene and the present. We predict a similar habitat loss between the present and 2070. The spatial patterns of habitat change support our hypothesis that koala extinctions in the southwest, Nullarbor Plain and central South Australia resulted from the eastward retraction of the dominant koala-browse species in response to long-term climate changes. Future climate patterns will likely increase the extinction risk of koalas in their remaining eastern ranges.