Information on the temporal stability of genetic structures is important to permit detection of changes that can constitute threats to biological resources. Large-scale harvesting operations are known to potentially alter the composition and reduce the variability of populations, and Atlantic herring (Clupea harengus) has a long history of heavy exploitation. In the Baltic Sea and Skagerrak waters, the census population sizes have declined by 35-50% over the last three decades. We compared the genetic structure of Atlantic herring in these waters sampled at least two different times between 1979 and 2003 by assaying 11 allozyme and nine microsatellite loci. We cannot detect any changes in the amount of genetic variation or spatial structure, and differentiation is weak with overall F(ST)=0.003 among localities for the older samples and F(ST)=0.002 for the newer ones. There are indications of temporal allele frequency changes, particularly in one of five sampling localities that is reflected in a relatively small local N(e) estimate of c. 400. The previously identified influence of selection at the microsatellite locus Cpa112 remains stable over the 24-year period studied here. Despite little genetic differentiation, migration among localities appears small enough to permit demographic independence between populations.