The region from New Guinea through Oceania sustains the world’s most diverse set of columbids. We describe osteological characters of the hindlimb (femur, tibiotarsus, tarsometatarsus) that divide the Papuan-Oceanic pigeons and doves into three groups based on functional morphology: “arboreal” (Hemiphaga, Ducula, Ptilinopus, Drepanoptila, Gymnophaps), “intermediate” (Columba, Macropygia, Reinwardtoena), and “terrestrial” (Gallicolumba [includes Alopecoenas], Trugon, Microgoura, Goura, Chalcophaps, Geopelia, Henicophaps, Caloenas, Didunculus, Otidiphaps). The arboreal and terrestrial groups are each distinctive osteologically, especially in the tibiotarsus and tarsometatarsus, which are short relative to the femur in the arboreal group, and long relative to the femur in the terrestrial group. The intermediate pigeons are more similar to arboreal than to terrestrial pigeons, but nonetheless fit in neither group. To estimate the phylogenetic relationships among or within these three groups is somewhat tentative using hindlimb osteology alone, although all five genera of arboreal pigeons have independent molecular evidence of relatedness, as do most of the genera of terrestrial pigeons. Using the hindlimb and other osteological data as a framework, we describe a new extinct genus and species of pigeon, Tongoenas burleyi, from Holocene archaeological and Pleistocene paleontological sites on six islands (Foa, Lifuka, `Uiha, Ha`afeva, Tongatapu, and `Eua) in the Kingdom of Tonga. Tongoenas was a large-sized member of the “arboreal” pigeon group, with osteological characters that relate it to Ducula, Gymnophaps, and Hemiphaga (generally canopy frugivores) rather than with the “terrestrial” pigeons (more ground-dwelling and granivorous) such as Gallicolumba, Trugon, Microgoura, Goura, etc. (others listed above). Among volant columbids, living or extinct, only the species of Goura (from New Guinea) are larger than Tongoenas. From most of the same prehistoric sites, we also report new material of the nearly as large, extinct pigeon Ducula shutleri Worthy & Burley, recently described from islands in the Vava`u Group of Tonga. Thus, D. shutleri also was widespread in Tonga before human impact. The prehistoric anthropogenic loss in Tonga of Tongoenas burleyi, Ducula shutleri, and other columbids undoubtedly had a negative impact on the dispersal regimes of Tongan forest trees. At first human contact about 2850 years ago, at least nine species of columbids in six genera inhabited the Tongan islands, where only four species in three genera exist today.