We conducted a phylogeographic study of the Gambel's Quail (Callipepla gambelii) using sequences of the mitochondrial control region and NADH dehydrogenase subunit 2 (ND2) obtained from 167 specimens including hunter–harvested wings and museum study skins. The Gambel's Quail exhibited strong phylogeographic structure, large genetic gaps, and relatively high levels of haplotype (Hd = 0.79) and nucleotide diversity (π = 0.01). Thirty-four Gambel's Quail haplotypes clustered into two distinct haplogroups, with two additional highly divergent haplotypes. Distribution of the haplogroups was not concordant with sampled subspecies or ecogeographic regions; however, the overall distribution of the two haplogroups suggests that the Gambel's Quail may have been isolated in separate refugia of the Chihuahuan and Sonoran deserts during the Pleistocene. Both haplogroups appear to have undergone recent demographic expansion, possibly related to climatic changes associated with the onset of drier conditions in southwestern North America following the end of the Last Glacial Maximum.