We studied mitochondrial genetic differentiation among nine taxa of large gulls of the Larus cachinnans-fuscus group, which form part of the circumpolar Herring Gull complex. Our primary interest was to see if there were unrecognized gene flow barriers, to what extent mitochondrial genetic population structure conformed to current taxonomic boundaries, and what it might reveal about possible differences in population history. Sequences (430 nucleotides) of the hypervariable control region I (HVR-I) were obtained from 580 individuals and proved highly informative within this recently diverged group of birds. Contrary to current classification, a basal split was revealed between an Atlantic-Mediterranean clade (atlantis, michahellis, armenicus) and a NW Palearctic-Central Asian clade (cachinnans, barabensis, mongolicus, fuscus-group). There was almost no mitochondrial gene flow between these two groups, although they are in geographical contact in two areas (eastern North Atlantic, Black Sea). Within each of the two major groups, there was strong phylogeographic structure with gene flow barriers between some neighbouring taxa (e.g. cachinanns vs. barabensis), but also a case of poor genetic differentiation between phenotypically distinct forms (barabensis vs. heuglini). At the subspecies level, current taxonomy corresponded well to molecular genetic structure: over 80% of the molecular genetic variance was partitioned among six (groups of) taxa. This is in sharp contrast to previous studies using allozymes and amplified fragment length polymorphism (AFLP) markers, which seemed to indicate extensive nuclear gene flow. Within-taxon haplotype phylogenies and mismatch distributions revealed contrasting demographic histories: cachinnans (Ponto-Caspian region) and atlantis (NE Atlantic) represent ancient lineages with large long-term population sizes, inland forms stem from very recent colonization events (barabensis, mongolicus) or passed through a population bottleneck (armenicus).