Little is known about how quickly natural populations adapt to changes in their environment and how temporal and spatial variation in selection pressures interact to shape patterns of genetic diversity. We here address these issues with a series of genome scans in four overfished populations of Atlantic cod (Gadus morhua) studied over an 80-year period. Screening of >1000 gene-associated single-nucleotide polymorphisms (SNPs) identified 77 loci that showed highly elevated levels of differentiation, likely as an effect of directional selection, in either time, space or both. Exploratory analysis suggested that temporal allele frequency shifts at certain loci may correlate with local temperature variation and with life history changes suggested to be fisheries induced. Interestingly, however, largely nonoverlapping sets of loci were temporal outliers in the different populations and outliers from the 1928 to 1960 period showed almost complete stability during later decades. The contrasting microevolutionary trajectories among populations resulted in sequential shifts in spatial outliers, with no locus maintaining elevated spatial differentiation throughout the study period. Simulations of migration coupled with observations of temporally stable spatial structure at neutral loci suggest that population replacement or gene flow alone could not explain all the observed allele frequency variation. Thus, the genetic changes are likely to at least partly be driven by highly dynamic temporally and spatially varying selection. These findings have important implications for our understanding of local adaptation and evolutionary potential in high gene flow organisms and underscore the need to carefully consider all dimensions of biocomplexity for evolutionarily sustainable management.