Despite the enormous economic and ecological importance of marine organisms, the spatial scales of adaptation and biocomplexity remain largely unknown. Yet, the preservation of local stocks that possess adaptive diversity is critical to the long-term maintenance of productive stable fisheries and ecosystems. Here, we document genomic evidence of range-wide adaptive differentiation in a broadcast spawning marine fish, Atlantic cod (Gadus morhua), using a genome survey of single nucleotide polymorphisms. Of 1641 gene-associated polymorphisms examined, 70 (4.2%) tested positive for signatures of selection using a Bayesian approach. We identify a subset of these loci (n=40) for which allele frequencies show parallel temperature-associated clines (p<0.001, r2=0.89) in the eastern and western north Atlantic. Temperature associations were robust to the statistical removal of geographic distance or latitude effects, and contrasted 'neutral' loci, which displayed no temperature association. Allele frequencies at temperature-associated loci were significantly correlated, spanned three linkage groups and several were successfully annotated supporting the involvement of multiple independent genes. Our results are consistent with the evolution and/or selective sweep of multiple genes in response to ocean temperature, and support the possibility of a new conservation paradigm for non-model marine organisms based on genomic approaches to resolving functional and adaptive diversity.