We examined the global mitochondrial phylogeography of Gyrodactylus arcuatus, a flatworm ectoparasite of three-spined stickleback Gasterosteus aculeatus. In accordance with the suggested high divergence rate of 13%/million years, the genetic variation of the parasite was high: haplotype diversity h = 0.985 and nucleotide diversity π = 0.0161. The differentiation among the parasite populations was substantial (Φ_st = 0.759), with two main allopatric clades (here termed Euro and North) accounting for 54% of the total genetic variation. The diversity center of the Euro clade was in the Baltic Sea, while the North clade was spread across the Barents and White Seas. A single haplotype within the North clade was found in the western and eastern Pacific Ocean. Divergence of main clades was estimated to be circa 200 thousand years ago. Each main clade was further divided into six distinct subclades, estimated to have diverged in isolation since 135 thousand years ago. This second division corresponds approximately to the Eemian interglacial predating the last glacial maximum. A demographic expansion of the subclades is associated with colonisation of northern Europe since the last glacial maximum, circa 15–40 thousand years ago. The parasite phylogeny is most likely explained by sequential isolated bottlenecks and expansions in numerous allopatric refugia. The postglacial intermingling and high variation in the marine parasite populations, separately in the Baltic and Barents Seas, suggest low competition of divergent parasite matrilines, coupled with a large population size and high rate of dispersal of hosts. The genetic contribution of the assumed refugial fish populations maintaining the parasite during the last glacial maximum was not detected among the marine sticklebacks, which perhaps were infected after range expansion.