Wombats (Vombatidae, Marsupialia) are fossorial marsupials that are most closely related to koalas amongst living marsupials. The cheek teeth of wombats are unique amongst Australian marsupials in being hypselodont (the condition where the teeth continue to grow throughout life and the formation of roots is suppressed). Hypselodonty is an adaptation to high degrees of tooth wear. The fossil record of vombatids is largely restricted to Pliocene to recent deposits and is largely represented by isolated teeth. Six genera are currently recognised from these deposits, all of which have hypselodont teeth. To date, a single isolated vombatid tooth has been described from pre-Pliocene deposits of South Australia and is the only example of a vombatid cheek tooth that possesses roots. Seventy specimens, representing five species of vombatid, have been recovered from Oligo-Miocene deposits in the Riversleigh World Heritage Site in northwestern Queensland and are described here. Among these are four new species and one new genus. A new species of Warendja from Riversleigh is described. It represents the oldest known hypselodont vombatid. This species is compared with additional specimens of the Pleistocene species of Warendja (W wakefieldi). Three species of Rhizophascolonus and a new monotypic genus are also described. Phylogenetic analysis of these taxa indicates that Rhizophascolonus may represent a sister taxon to the other vombatids. These specimens comprise almost all known examples of Oligo-Miocene vombatids. Most of the specimens are isolated teeth and are highly variable in size and morphology. Cusp detail is clearly preserved on many, allowing for omparison with the cusp morphology on juvenile cheek teeth of the common wombat (Vombatus ursinus). All of the taxa found in the deposits at Riversleigh share a number of characters such as marked differences in enamel thickness and height around the cheek teeth. It is argued here that these shared characters are indicative of high amounts of tooth wear and/or occlusal stresses acting on the trailing edge enamel. Combined with evidence of scratch-digging adaptations of the forelimbs it is suggestive of a rhizophagous niche for at least some of these early vombatids.