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, which in itself may result in reproductive isolation caused by natural selection on immigrants. 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.