Spatial and temporal population genetic structures of the common sole, Solea solea, were studied in Northeastern Atlantic and Mediterranean Sea populations, using three polymorphic exon-primed intron-crossing (EPIC) markers. Results demonstrated significant multilocus differentiation among Eastern Mediterranean and a group composed by Western Mediterranean and Atlantic populations (theta = 0.150, P < 0.001), but also suggested unrecorded genetic differentiation of the Adriatic Sea population. No pattern of isolation-by-distance was recorded across the range covered by sampling, from the Kattegat to the Aegean Sea. Conversely to genetically structured Mediterranean populations, Atlantic populations ranging from Denmark to Portugal could be considered as representative of the same panmictic unit (theta = 0.009, not significant). Results further demonstrated stability of multilocus genetic structure among temporarily replicated cohort samples [0+, 1+, subadults] from several coastal and estuarine locations from Bay of Biscay, excepted for the amylase locus Am2B3-2 at one location (Pertuis d'Antioche). Despite coherence of such observed patterns of multilocus differentiation with previous allozymic surveys in sole, and with patterns generally obtained for other marine fish species, single-locus results from EPICs indicated divergent coalescence schemes supporting a complex response to ecology and history of sole's populations. Results stress the use of nuclear genes such as EPIC markers to investigate population structure, but also historical, demographic, and possibly selective processes in marine fishes.