Regulations on the exploitation of populations of commercially important fish species and the ensuing consumer interest in sustainable products have increased the need to accurately identify the population of origin of fish and fish products. Although genomics-based tools have proven highly useful, there are relatively few examples in marine fish displaying accurate origin assignment. We synthesize data for 156 single-nucleotide polymorphisms typed in 1039 herring, Clupea harengus L., spanning the Northeast Atlantic to develop a tool that allows assignment of individual herring to their regional origin. We show the method's suitability to address specific biological questions, as well as management applications. We analyse temporally replicated collections from two areas, the Skagerrak (n = 81, 84, 66) and the western Baltic (n = 52, 52). Both areas harbour heavily fished mixed-origin stocks, complicating management issues. We report novel genetic evidence that herring from the Baltic Sea contribute to catches in the North Sea, and find support that western Baltic feeding aggregations mainly constitute herring from the western Baltic with contributions from the Eastern Baltic. Our study describes a general approach and outlines a database allowing individual assignment and traceability of herring across a large part of its East Atlantic distribution.