Climate variability is now known to play a key role in the abundance of marine fisheries, and must be accounted for to implement sustainable management strategies. We show that North American Atlantic salmon abundance has fluctuated in parallel with the Atlantic Multidecadal Oscillation (AMO); a basin-wide, low frequency climate mode producing cold-warm-cold sea surface temperatures over the last century. During the AMO warm (cool) phase salmon abundance is lower (higher). Changes in sea surface temperature associated with the AMO are most pronounced in the winter season near the Grand Banks of Newfoundland, a known overwintering area for salmon and an important time for determining survival. A moratorium on salmon fishing was established in 1992, but has so far contributed few signs of improvement in stock size. This may be explained by a shift in the AMO to a positive phase, producing persistently warm temperatures in the marine environment. Our findings show that a continued warming near the Grand Banks of Newfoundland will have a detrimental impact on this already depleted stock despite the reduction in commercial fishing.