A fossil coracoid from Late Oligocene deposits at Riversleigh, north-western Queensland, is described as a new genus and species of pigeon (Aves:Columbidae), which, based on a unique set of shared characters, is most closely allied to the Australian bronzewings, and Phaps in particular. This, the first described fossil pigeon from pre-Quaternary deposits of Australia, demonstrates that phabine pigeons were present in the Late Oligocene to Early Miocene (c. 26-24 million years ago), supporting molecular-based hypotheses for the age of this clade. Two other fragmentary fossils from South Australia attest to at least one other species of pigeon being present in Australia at this time, but they are too incomplete for their affinity to be narrowed further. The new fossils are the oldest columbid fossils globally and although few in number indicate that a diversity of taxa, including the precursors of Australian bronzewings were present in Australia by the end of the Paleogene. This emerging fossil record of pigeons supports ages of divergence of clades based on molecular analyses and suggests that Australia has had a long role in columbid evolution.