How species genetically adapt to new environments is a central question in evolutionary biology. Here whole-genome sequencing combined with functional analysis is used to dissect how Atlantic herring, a marine fish, has adapted to the brackish Baltic Sea. Genes involved in reproduction and early development emerge as primary targets of natural selection, with key changes in a sperm-specific anion channel (LRRC8C2), a zona pellucida protein (ZPBA1), a cluster of three genes for fish transglutaminase (FTG1-3), and a copy number expansion of a fish hatching enzyme gene (HE1C). The large diameter of LRRC8C2 homomers facilitates transport of ions and osmolytes, likely preventing swelling of sperm when spawning in low salinity. Altered ZPBA1 sequence together with modified FTG1-3 enzyme activity produces a harder egg envelope that prevents egg swelling in brackish waters, while the enhanced activity of the adapted HE1C enzyme enables larvae to digest this reinforced egg envelope during hatching. Baltic Sea herring populations reproducing in brackish water are fixed or nearly fixed for variant alleles at these four unlinked loci, each carrying multiple amino acid substitutions compared to the alleles prevalent in the Atlantic Ocean populations. The alleles at two of these loci (FTG1-3, and HE1C) have been introgressed from the sister species Pacific herring. These findings reveal concrete molecular mechanisms by which a marine species has adapted to a novel, low-salinity environment.