We studied the influence of glacial oscillations on the genetic structure of seven species of white-headed gull that breed at high latitudes (Larus argentatus, L. canus, L. glaucescens, L. glaucoides, L. hyperboreus, L. schistisagus, and L. thayeri). We evaluated localities hypothesized as ice-free areas or glacial refugia in other Arctic vertebrates using molecular data from 11 microsatellite loci, mitochondrial DNA (mtDNA) control region, and six nuclear introns for 32 populations across the Holarctic. Moderate levels of genetic structure were observed for microsatellites (F(ST)= 0.129), introns (Φ(ST)= 0.185), and mtDNA control region (Φ(ST)= 0.461), with among-group variation maximized when populations were grouped based on subspecific classification. Two haplotype and at least two allele groups were observed across all loci. However, no haplotype/allele group was composed solely of individuals of a single species, a pattern consistent with recent divergence. Furthermore, northernmost populations were not well differentiated and among-group variation was maximized when L. argentatus and L. hyberboreus populations were grouped by locality rather than species, indicating recent hybridization. Four populations are located in putative Pleistocene glacial refugia and had larger τ estimates than the other 28 populations. However, we were unable to substantiate these putative refugia using coalescent theory, as all populations had genetic signatures of stability based on mtDNA. The extent of haplotype and allele sharing among Arctic white-headed gull species is noteworthy. Studies of other Arctic taxa have generally revealed species-specific clusters as well as genetic structure within species, usually correlated with geography. Aspects of white-headed gull behavioral biology, such as colonization ability and propensity to hybridize, as well as their recent evolutionary history, have likely played a large role in the limited genetic structure observed.