We analyzed 2995 base pairs of nucleotide sequence data (nuclear beta-fibrinogen intron 7 and mitochondrial cytochrome b and ND2 genes), using parsimony and model-based approaches to infer phylogenetic relationships of the woodpeckers and allies, yielding novel hypotheses for several critical gaps in the knowledge of picid phylogeny. We tested the monophyly of sub-families within the Picidae, and sampled from widely distributed and diverse genera (Celeus, Colaptes, Dryocopus, Melanerpes, Picoides, Picumnus, Sasia, Piculus, and Picus). Relationships of three poorly known Southeast Asian genera (Dinopium, Reinwardtipicus, and Blythipicus) were also examined, revealing unexpected sister relationships. All phylogenetic approaches recovered largely congruent topologies, supporting a monophyletic Picinae and paraphyletic Picumninae, with the monotypic piculet, Nesoctites micromegas, as sister to the Picinae. We report paraphyly for Celeus and Piculus, whereas the broadly distributed genera Picumnus and Dryocopus were supported as monophyletic. Our phylogenetic results indicate a complex geographic history for the Picidae, with multiple disjunct sister lineages distributed between the New World and Asia. The relationships and geographic distribution of basal picid lineages indicates an Old World origin of the Picidae; however, the geographic origin of the Picinae remains equivocal, as the sister relationship between the Caribbean N. micromegas and the true woodpeckers presents the possibility of a New World origin for the Picinae.