Studies of colonization of new habitats that appear from rapidly changing environments are interesting and highly relevant to our understanding of divergence and speciation. Here, we analyse phenotypic and genetic variation involved in the successful establishment of a marine fish (sand goby, Pomatoschistus minutus) over a steep salinity drop from 35 PSU in the North Sea (NE Atlantic) to two PSU in the inner parts of the post-glacial Baltic Sea. We first show that populations are adapted to local salinity in a key reproductive trait, the proportion of motile sperm. Thereafter, we show that genome variation at 22,190 single nucleotide polymorphisms (SNPs) shows strong differentiation among populations along the gradient. Sequences containing outlier SNPs and transcriptome sequences, mapped to a draft genome, reveal associations with genes with relevant functions for adaptation in this environment but without overall evidence of functional enrichment. The many contigs involved suggest polygenic differentiation. We trace the origin of this differentiation using demographic modelling and find the most likely scenario is that at least part of the genetic differentiation is older than the Baltic Sea and is a result of isolation of two lineages prior to the current contact over the North Sea–Baltic Sea transition zone.