We describe range-wide phylogeographic variation in the Black-headed Grosbeak (Pheucticus melanocephalus), a songbird that is widely distributed across North American scrublands and forests. Phylogenetic analysis of mitochondrial DNA (mtDNA, n = 424) revealed three geographically structured clades. One widespread clade occurs throughout the Rocky Mountains, Great Basin, and Mexican Plateau, a second clade is found on the Pacific coast and in coastal ranges; and, a third in the Sierra Madre del Sur of Oaxaca and Guerrero. Some geographical structuring occurs in Mexican Plateau and Sierra Madre Oriental mtDNA clade, presumably because these populations have been more stable over time than northern populations. Multiple mitochondrial groups are found sympatrically in the Okanogan River Valley in Washington, the eastern Sierra Nevada, and the Transvolcanic Belt across central Mexico, indicating that there is a potential for introgression. Analyses of 12 nuclear loci did not recover the same geographically structured clades. Population analyses show high levels of gene flow in nucDNA from the Interior into the Sierra Madre del Sur and Pacific population groups, possibly indicating expansion of the Interior population at the expense of peripheral populations.