Understanding whether natural populations are adapted to their local environments and how quickly they may evolve in face of altered conditions is important for predicting responses to global change and other anthropogenic impacts. Previously, it was expected that local adaptation would be absent or rare in marine fish such as Atlantic cod that presumably exhibits high levels of gene flow. Yet, recent evidence has suggested widespread adaptive divergence in this species, even over small geographic scales. In light of parallel reports of drastic fisheries-induced adaptive changes over decadal time scales, it remains uncertain, however, how important temporal variation in selection pressures within single populations are – relative to spatial variation – for shaping patterns of genetic diversity and adaptation. We here address this issue by analyzing historical DNA samples that provide unique opportunities to study microevolution directly at the genomic level in retrospective real time. Using recently developed high-throughput genotyping methods, we screened the temporal and spatial variation in › 1000 gene-associated single nucleotide polymorphisms (SNPs) across four populations of Atlantic cod over a period of up to 80 years. We identified 28 loci that showed highly elevated levels of differentiation ('outliers'), likely an effect of selection, in either time, space or both. Surprisingly, largely non-overlapping sets of loci were temporal outliers in the different populations and outliers from an early period showed almost complete stability during later periods. The contrasting micro-evolutionary trajectories among populations resulted in sequential shifts among spatial outliers, with no locus maintaining elevated differentiation throughout the study period. Simulations coupled with observations of significant temporally stable spatial structure at neutral loci suggest that population replacement or shifting migration patterns alone cannot explain the observed allele frequency variation, indicating that highly dynamic temporally and spatially varying selection has likely been important for shaping the observed patterns. 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 biocomplexity in fisheries management.