The bowerbirds (Passeriformes, Ptilonorhynchidae) are a family of Australo-Papuan songbirds that are renowned for their unique bower-building behaviour. Prior to this study, the fossil record of Ptilonorhynchidae was limited to late Quaternary remains from Victoria, Australia. A new genus and species of bowerbird is described here from the late Oligocene (ca 26–23 Ma) deposits of the Riversleigh World Heritage Area, in Waanyi Country, Queensland, Australia. This fossil bowerbird is smaller than most extant species of bowerbirds, and represents the earliest known evidence of Ptilonorhynchidae, although its intrafamilial affinities remain uncertain pending additional material. A second, larger ptilonorhynchid is identified from the early Miocene (ca 16 Ma) of Riversleigh. These fossils considerably extend the temporal range of Ptilonorhynchidae, and indicate the presence of two species of bowerbirds in the Oligo-Miocene of northern Australia. The ages of these fossils are consistent with molecular estimates of the divergence time between Ptilonorhynchidae and its sister group, Climacteridae (Australo-Papuan treecreepers). The new bowerbird is the ninth species of passerine to be described from the pre-Pleistocene of Australia, and highlights the importance of the Riversleigh fossil deposits in our understanding of the early evolutionary history of passerines. Jacqueline M.T. Nguyen [firstname.lastname@example.org], Australian Museum Research Institute, 1 William Street, Sydney NSW 2010 Australia; College of Science and Engineering, Flinders University, GPO Box 2100, Adelaide SA 5001 Australia; and South Australian Museum, North Terrace, Adelaide SA 5000 Australia.