The world’s oceans are currently facing major stressors in the form of overexploitation and anthropogenic climate change. The Baltic Sea was home to the first “industrial” fishery ∼800 y ago targeting the Baltic herring, a species that is still economically and culturally important today. Yet, the early origins of marine industries and the long-term ecological consequences of historical and contemporary fisheries remain debated. Here, we study long-term population dynamics of Baltic herring to evaluate the past impacts of humans on the marine environment. We combine modern whole-genome data with ancient DNA (aDNA) to identify the earliest-known long-distance herring trade in the region, illustrating that extensive fish trade began during the Viking Age. We further resolve population structure within the Baltic and observe demographic independence for four local herring stocks over at least 200 generations. It has been suggested that overfishing at Øresund in the 16th century resulted in a demographic shift from autumn-spawning to spring-spawning herring dominance in the Baltic. We show that while the Øresund fishery had a negative impact on the western Baltic herring stock, the demographic shift to spring-spawning dominance did not occur until the 20th century. Instead, demographic reconstructions reveal population trajectories consistent with expected impacts of environmental change and historical reports on shifting fishing targets over time. This study illustrates the joint impact of climate change and human exploitation on marine species as well as the role historical ecology can play in conservation and management policies.