Diprotodontians are the morphologically and ecologically most diverse order of marsupials. However, an approximately 30-million-year gap in the Australian terrestrial vertebrate fossil record means that the first half of diprotodontian evolution is unknown. Fossil taxa from immediately either side of this gap are therefore critical for reconstructing the early evolution of the order. Here we report the likely oldest-known koala relatives (Phascolarctidae), from the late Oligocene Pwerte Marnte Marnte Local Fauna (central Australia). These include coeval species of Madakoala and Nimiokoala, as well as a new probable koala (?Phascolarctidae). The new taxon, Lumakoala blackae gen. et sp. nov., was comparable in size to the smallest-known phascolarctids, with body-mass estimates of 2.2–2.6 kg. Its bunoselenodont upper molars retain the primitive metatherian condition of a continuous centrocrista, and distinct stylar cusps B and D which lacked occlusion with the hypoconid. This structural arrangement: (1) suggests a morphocline within Phascolarctidae from bunoselenodonty to selenodonty; and (2) better clarifies the evolutionary transitions between molar morphologies within Vombatomorphia. We hypothesize that the molar form of Lumakoala blackae approximates the ancestral condition of the suborder Vombatiformes. Furthermore, it provides a plausible link between diprotodontians and the putative polydolopimorphians Chulpasia jimthorselli and Thylacotinga bartholomaii from the early Eocene Tingamarra Local Fauna (eastern Australia), which we infer as having molar morphologies consistent with stem diprotodontians.