The phylogeographical patterns of a small marine fish, the common goby, Pomatoschistus microps, were assessed at 12 sites along the northeastern Atlantic coasts and the western Mediterranean Sea. A combination of two genetic markers was employed: cellulose acetate allozyme electrophoresis (CAGE) and sequence analysis of a 289 bp fragment of the mitochondrial locus cytochrome b. Both markers were congruent in revealing significant differences between samples (global FST = 0.247 for the allozymes and PhiST = 0.437 for the mitochondrial DNA data) and a pattern of isolation-by-distance. Phylogeographical analyses yielded a shallow branching structure with four groups. Three of those were confined to the Atlantic basin and showed a star-like pattern. The fourth group contained a central haplotype occurring at the edges of the species' distribution, accompanied by a few more rare variants, which were restricted to the Mediterranean Sea. A genetic break was observed around the British Isles, with distinct haplotypes dominating at either side of the English Channel. A significantly negative correlation between the degree of genetic diversity and latitude was recorded both for mitochondrial DNA (mtDNA) and allozymes in the Atlantic basin. Gene flow analysis suggested that recolonization of the North Sea and the coasts of western Scotland and Ireland may have taken place from a glacial refugium in the Southern Bight of the North Sea. These results are discussed in the perspective of possible postglacial migration routes of marine fish along the northeastern Atlantic coasts.