Wild populations of Atlantic salmon have declined worldwide. While the causes for this decline may be complex and numerous, increased mortality at sea is predicted to be one of the major contributing factors. Examining the potential changes occurring in the genome-wide composition of populations during this migration has the potential to tease apart some of the factors influencing marine mortality. Here, we genotyped 5568 SNPs in Atlantic salmon populations representing two distinct regional genetic groups and across two cohorts to test for differential allelic and genotypic frequencies between juveniles (smolts) migrating to sea and adults (grilses) returning to freshwater after one year at sea. Given the complexity of the traits potentially associated with sea mortality, we contrasted the outcomes of a single-locus FST based genome scan method with a new multi-locus framework to test for genetically-based differential mortality at sea. While numerous outliers were identified by the single-locus analysis, no evidence for parallel, temporally repeated selection was found. In contrast, the multi-locus approach detected repeated patterns of selection for a multi-locus group of 34 co-varying SNPs in one of the two populations. No significant pattern of selective mortality was detected in the other population, suggesting different causes of mortality among populations. These results first support the hypothesis that selection mainly causes small changes in allele frequencies among many co-varying loci rather than a small number of changes in loci with large effects. They also point out that moving away from the a strict “selective sweep paradigm” towards a multi-locus genetics framework may be a more useful approach for studying the genomic signatures of natural selection on complex traits in wild populations.