Small pelagic fish support profitable fisheries and are important for food security around the world. Yet, their sustainable management can be hindered by the indiscriminate impacts of simultaneous exploitation of fish from multiple distinct biological populations over extended periods of time. The quantification of such impacts is greatly facilitated by recently developed molecular tools—including diagnostic single nucleotide polymorphism (SNP) panels for mixed-stock analysis (MSA)—that can accurately detect the population identity of individual fish. However, the biological relevance of such tools over longer periods of time remains unknown. Here, we demonstrate that diagnostic SNP panels designed for contemporary MSA in Atlantic herring have a millennium-long biological relevance and applicability. We assign the population identity of ancient Atlantic herring specimens—obtained through famously profitable historic fisheries—up to 1300 years old from eight archaeological sites across Europe. Analyzing contemporary and ancient whole-genome data, we obtain evidence for the long-term mixed-stock exploitation of Atlantic herring. Despite such mixed-stock exploitation, we exclusively identify autumn-spawning herring amongst these archaeological remains, indicative of a specific biological availability or cultural preference for certain herring ecotypes in the past. Moreover, our results show that herring demographic patterns were relatively stable until the dramatic disruptions and stock collapses during the 20th century. We find small but significant reductions in genetic diversity over time, indicating long-term evolutionary consequences from 20th-century stock declines. The long-term applicability of diagnostic SNP panels underscores their biological relevance and cost-effective application for the genetic monitoring of herring stocks and highlights the utility of ancient DNA to obtain insights in herring ecology and population dynamics.Mitonuclear discordance between species is readily documented in marine fishes. Such discordance may either be the result of past natural phenomena or the result of recent introgression from previously seperated species after shifts in their spatial distributions. Using ancient DNA spanning five millennia, we here investigate the long-term presence of Pacific bluefin tuna (Thunnus orientalis) and albacore (Thunnus alalunga) -like mitochondrial (MT) genomes in Atlantic bluefin tuna (Thunnus thynnus), a species with extensive exploitation history and observed shifts in abundance and age structure. Comparing ancient (n = 130) and modern (n = 78) Atlantic bluefin MT genomes from most of its range, we detect no significant spatial or temporal population structure, which implies ongoing gene flow between populations and large effective population sizes over millennia. Moreover, we identify discordant MT haplotypes in ancient specimens up to 5000 years old and find that the frequency of these haplotypes has remained similar through time. We therefore conclude that MT discordance in the Atlantic bluefin tuna is not driven by recent introgression. Our observations provide oldest example of directly observed MT discordance in the marine environment, highlighting the utility of ancient DNA to obtain insights in the long-term persistence of such phenomena.