Logrunners (Orthonychidae) are a family of ground-dwelling passerines that are endemic to the Australo-Papuan region. These peculiar birds are part of an ancient Australo-Papuan radiation that diverged basally in the oscine tree. Here we describe eight fossil tarsometatarsi of the logrunner Orthonyx kaldowinyeri, and a distal tibiotarsus tentatively assigned to this species from sites in the Riversleigh World Heritage Area, Australia. The new fossil material ranges in age from late Oligocene to early late Miocene, and extends the temporal range of the Orthonychidae into the late Oligocene; this is the geologically oldest record of the family. These specimens also include the oldest Cenozoic passerine fossils from Australia that can be confidently referred to an extant family. The distinctive features of the tarsometatarsus and tibiotarsus of extant logrunners, which are probably related to their unusual method of foraging, are also present in O. kaldowinyeri. Assuming that O. kaldowinyeri had vegetation requirements similar to those of extant logrunners, its presence in various Riversleigh sites provides clues about the palaeoenvironment of these sites.