Little is known about local adaptations in marine fishes since population genetic surveys in these species have typically not applied genetic markers subject to selection. In this study, we used a candidate gene approach to investigate adaptive population divergence in the European flounder (Platichthys flesus L.) throughout the northeastern Atlantic. We contrasted patterns of genetic variation in a presumably neutral microsatellite baseline to patterns from a heat-shock cognate protein gene, Hsc70. Using two different neutrality tests we found that the microsatellite data set most likely represented a neutral baseline. In contrast, Hsc70 strongly deviated from neutral expectations. Importantly, when estimating standardized levels of population divergence (F(ST)'), we also found a large discrepancy in the patterns of structuring in the two data sets. Thus, samples grouped according to geographical or historical proximity with regards to microsatellites, but according to environmental similarities with regards to Hsc70. The differences between the data sets were particularly pronounced in pairwise comparisons involving populations in the western and central Baltic Sea. For instance, the genetic differentiation between geographically close Baltic Sea and North Sea populations was found to be 0.02 and 0.45 for microsatellites and Hsc70 respectively. Our results strongly suggest adaptive population divergence and indicate local adaptations at the DNA level in a background of high levels of gene flow, typically found in many marine fish species. Furthermore, this study highlights the usefulness of the candidate gene approach for demonstrating local selection in non-model organisms such as most marine fishes.