Koalas (Phascolarctidae, Marsupialia) are generally rare components of the Australian fossil record. However, new specimens of fossil koalas were recovered during recent systematic excavations from several eastern Plio-Pleistocene deposits of Queensland, eastern Australia, including the regions of Chinchilla, Marmor and Mt. Etna. The new records are significant in that they extend the temporal and geographic range of Plio-Pleistocene koalas from southern and southeastern Australia, to northeastern central Queensland. We provide the first unambiguous evidence of koalas in the Pliocene Chinchilla Local Fauna (phascolarctid indet. and Ph. ?stirtoni): important additions to an increasingly diverse arboreal mammalian assemblage that also includes tree kangaroos. The persistence of koalas and local extinction of tree kangaroos in the Chinchilla region today suggests that significant habitat and faunal reorganization occurred between the Pliocene and Recent, presumably reflecting the expansion of open woodlands and grasslands. Other koala records from the newly U/Th-dated Middle Pleistocene Marmor and Mt. Etna fossil deposits (Phascolarctos sp. and Ph. ?stirtoni), along with independent palaeohabitat proxies, indicate the former presence of heterogeneous habitats comprised of rainforests, open woodlands and grasslands. The lack of such habitat mosaics in those regions today is likely the product of significant Middle Pleistocene climate change.