Phylogenetic relationships among genera of pigeons and doves (Aves, Columbiformes) have not been fully resolved because of limited sampling of taxa and characters in previous studies. We therefore sequenced multiple nuclear and mitochondrial DNA genes totaling over 9000 bp from 33 of 41 genera plus 8 outgroup taxa, and, together with sequences from 5 other pigeon genera retrieved from GenBank, recovered a strong phylogenetic hypothesis for the Columbiformes. Three major clades were recovered with the combined data set, comprising the basally branching New World pigeons and allies (clade A) that are sister to Neotropical ground doves (clade B), and the Afro-Eurasian and Australasian taxa (clade C). None of these clades supports the monophyly of current families and subfamilies. The extinct, flightless dodo and solitaires (Raphidae) were embedded within pigeons and doves (Columbidae) in clade C, and monophyly of the subfamily Columbinae was refuted because the remaining subfamilies were nested within it. Divergence times estimated using a Bayesian framework suggest that Columbiformes diverged from outgroups such as Apodiformes and Caprimulgiformes in the Cretaceous before the mass extinction that marks the end of this period. Bayesian and maximum likelihood inferences of ancestral areas, accounting for phylogenetic uncertainty and divergence times, respectively, favor an ancient origin of Columbiformes in the Neotropical portion of what was then Gondwana. The radiation of modern genera of Columbiformes started in the Early Eocene to the Middle Miocene, as previously estimated for other avian groups such as ratites, tinamous, galliform birds, penguins, shorebirds, parrots, passerine birds, and toucans. Multiple dispersals of more derived Columbiformes between Australasian and Afro-Eurasian regions are required to explain current distributions.