Aim The Pleistocene glaciations were the most significant historical event during the evolutionary life span of most extant species. However, little is known about the consequences of these climate changes for the distribution and demography of marine animals of the north-eastern Atlantic. The present study focuses on the phylogeographic and demographic patterns of the sand goby, Pomatoschistus minutus (Teleostei: Gobiidae), a small marine demersal fish. Location North-eastern Atlantic, Mediterranean, Irish, North and Baltic seas. Methods Analysis was carried out by sequencing the mtDNA cytochrome b gene of sand gobies from 12 localities throughout the species' range, and using this information in combination with published data of allozyme markers and mtDNA control region sequences. Several phylogenetic methods and a network analysis were used to explore the phylogeographic pattern. The historical demography of P. minutus was studied through a mismatch analysis and a Bayesian skyline plot. Results Reciprocal monophyly was found between a Mediterranean Sea (MS) clade and an Atlantic Ocean (AO) clade, both with a Middle Pleistocene origin. The AO Clade contains two evolutionary significant units (ESUs): the Iberian Peninsula (IB) Group and the North Atlantic (NA) Group. These two groups diverged during Middle Pleistocene glacial cycles. For the NA Group there is evidence for geographic sorting of the ancestral haplotypes with recent radiations in the Baltic Sea, Irish Sea, North Sea and Bay of Biscay. The demographic histories of the Mediterranean Clade and the two Atlantic ESUs were influenced mainly by expansions dated as occurring during the Middle Pleistocene glaciations and post-Eem, respectively. Main conclusions The pre-LGM (Last Glacial Maximum) subdivision signals were not erased for P. minutus during the LGM. Middle Pleistocene glaciations yielded isolated and differently evolving sets of populations. In contrast to the case for most other taxa, only the northern Atlantic group contributed to the post-glacial recolonization. The historical demography of Mediterranean sand gobies was influenced mainly by Middle Pleistocene glaciations, in contrast to that of the Atlantic populations, which was shaped by Late Pleistocene expansions.