Freezing of herring (Clupea harengus) for human consumption is increasing in the Nordic herring industry, either onboard the fishing vessels or right after landing. The quality of frozen herring as a raw material does not only depend on the frozen storage conditions applied, but also on compositional features, something which in turn can vary with season and catching ground. To unravel the link between biological variations, basic muscle composition, and sensory properties of frozen herring, a unique herring raw material was caught by commercial fishing vessels at three locations: around Iceland, outside the Norwegian coast, and in Kattegat/Skagerrak. The samplings were done according to a specific scheme and conducted over several seasons and 2 years. The herring was converted into butterfly fillets, packed in cardboard boxes, frozen, and then stored at –20 °C or –80 °C for up to 18 mo. The sensory quality was characterized by objective sensory profiling. It was shown that two generalized sensory variables could be defined from a principal component analysis of the sensory data. Except for the expected pronounced effect from storage time, the most distinct variation followed the lipid content, which in turn varied with season. An unexpected conclusion was that catching location only had a minor affect on the changes in sensory quality of herring during frozen storage. Knowledge about how season and catching location affect herring during frozen storage will be useful for optimizing the utilization of herring for frozen storage for human consumption.