Quail-thrushes (Passeriformes: Cinclosomatidae: Cinclosoma) are ground-dwelling corvoid songbirds endemic to Austra lia and New Guinea. Until now, the only known quail-thrush fossils have been from late Quaternary cave deposits in Australia. A new species of quail-thrush, Cinclosoma elachum sp. nov., is described from the early to middle Miocene deposits in the Riversleigh World Heritage Area, Queensland, Australia. A second, larger quail-thrush is identified from the middle Miocene of Riversleigh. The new fossils considerably extend the geographic and temporal ranges of cinclosomatids, and indicate the presence of two species of quail-thrushes in the Miocene of northern Australia, located more than 300 km from the nearest extant member of Cinclosoma. These fossils provide a minimum age of~ 18 million years for Cinclosomatidae. They cannot be confidently assigned to the crown group of the genus Cinclosoma, but can be used to calibrate the split between this genus and Ptilorrhoa in molecular dating studies of the Corvides radiation and Passeriformes overall. This material also adds to the growing diversity of songbirds identified from the pre-Pleistocene record of Australia, and reemphasises the global significance of the Riversleigh deposits in developing understanding about the early evolutionary history of passerines.