Changing environmental conditions can lead to population diversification through differential selection on standing genetic variation. Structural variant (SV) polymorphisms provide examples of ancient alleles that in time become associated with novel environmental gradients. The European plaice (Pleuronectes platessa) is a marine flatfish showing large allele-frequency differences at two putative SVs associated with environmental variation. In this study, we explored the contribution of these SVs to population structure across the North East Atlantic. We compared genome-wide population structure using sets of RAD-sequencing SNPs with the spatial structure of the SVs. We found that in contrast to the rest of the genome, the SVs were only weakly associated with an isolation-by-distance pattern. Indeed, both SVs showed important variation in haplogroup frequencies, with the same haplogroup increasing both along the salinity gradient of the Baltic Sea, and found in high frequency in the northern-range margin of the Atlantic. Phylogenetic analyses suggested that the SV alleles are much older than the age of the Baltic Sea itself. These results suggest that the SVs are older than the age of the environmental gradients with which they currently co-vary. Altogether, our results suggest that the plaice SVs were shaped by evolutionary processes occurring at two time frames, firstly following their origin, ancient spread and maintenance in the ancestral populations, and secondly related to their current association with more recently formed environmental gradients such as those found in the North Sea-Baltic Sea transition zone.