Evolutionary divergence among populations occupying ecologically distinct environments can occur even in the face of on-going gene flow. However, the genetic underpinnings, as well as the scale and magnitude at which this differentiation occurs in marine habitats are not well understood. We investigated the patterns and degree of genomic heterogeneity in threespine sticklebacks (Gasterosteus aculeatus) by assessing genetic variability in 20 nongenic and 20 genic (associated with genes important for freshwater adaptation) microsatellite loci in samples collected from 38 locations spanning the entire Baltic Sea coast to the North Sea boundary. Population divergence (FST ≈ 0.026) and structuring (five genetic clusters) was significantly more pronounced in the genic as compared to nongenic markers (FST ≈ 0.008; no genetic clusters). Patterns of divergence in the genic markers—45% of which were identified as outliers—correlated with local differences in salinity. Yet, a strong positive correlation between divergence in genic and nongenic markers, and their association with environmental factors suggests that adaptive divergence is reducing gene flow across the genome. Apart from providing a clear demonstration of heterogeneous genomic patterns of differentiation in a marine species, the results are indicative of adaptive population structuring across the relatively young Baltic Sea in spite of ample opportunities for gene flow.