The relative importance of the Pleistocene glacial cycles in driving avian speciation remains controversial, partly because species limits in many groups remain poorly understood, and because current taxonomic designations are often based on phenotypic characteristics of uncertain phylogenetic significance. We use mtDNA sequence data to examine patterns of genetic variation, sequence divergence and phylogenetic relationships between phenotypically distinct groups of the yellow-rumped warbler complex. Currently classified as a single species, the complex is composed of two North American migratory forms (myrtle warbler Dendroica coronata coronata and Audubon's warbler Dendroica coronata auduboni), and two largely sedentary forms: Dendroica coronata nigrifrons of Mexico, and Dendroica coronata goldmani of Guatemala. The latter are typically considered to be races of the Audubon's warbler based on plumage characteristics. However, mtDNA sequence data reveal that sedentary Mesoamerican forms are reciprocally monophyletic to each other and to migratory forms, from which they show a long history of isolation. In contrast, migratory myrtle and Audubon's warblers form a single cluster due to high levels of shared ancestral polymorphism as evidenced by widespread sharing of mtDNA haplotypes despite marked phenotypic differentiation. Sedentary and migratory forms diverged in the early Pleistocene, whereas phenotypic differentiation between the two migratory forms has occurred in the Holocene and is likely the result of geographical isolation and subsequent range expansion since the last glaciation. Our results underscore the importance of Quaternary climatic events in driving songbird speciation and indicate that plumage traits can evolve remarkably fast, thus rendering them potentially misleading for inferring systematic relationships.