The Atlantic herring (Clupea harengus), one of the most abundant marine fishes in the world, has historically been a critical food source in Northern Europe. It is one of the few marine pecies that can reproduce throughout the brackish salinity gradient of the Baltic Sea. Previous studies based on few genetic markers have revealed a conspicuous lack of genetic differentiation between geographic regions, consistent with huge population sizes and minute genetic drift. Here, we present a cost-effective genome-wide study in a species that lacks a genome sequence. We first assembled a muscle transcriptome and then aligned genomic reads to the transcripts, creating an “exome assembly,” capturing both exons and flanking sequences. We then resequenced pools of fish from a wide geographic range, including the Northeast Atlantic, as well as different regions in the Baltic Sea, aligned the reads to the exome assembly, and identified 440,817 SNPs. The great majority of SNPs showed no appreciable differences in allele frequency among populations; however, several thousand SNPs showed striking differences, some approaching fixation for different alleles. The contrast between low genetic differentiation at most loci and striking differences at others implies that the latter category primarily reflects natural selection. A simulation study confirmed that the distribution of the fixation index F_ST deviated significantly from expectation for selectively neutral loci. This study provides insights concerning the population  structure of an important marine fish and establishes the Atlantic herring as a model for population genetic studies of adaptation and natural selection.