Sea level pressure (SLP) difference across Fram Strait is used as a proxy for ice export through the Strait to verify that a secular change in the link between the NAO and Fram Strait ice export occurred around 1980, and that the change was associated with an eastward shift in the SLP pattern associated with the NAO. Two additional variables, Siberian winter temperature, and an index of North Atlantic storm activity, are also found to switch from being uncorrelated with the ice export proxy in the 1950's and 60's to being strongly correlated in the 1980's and 90's, suggesting the emergence of a new climate regime associated with the NAO. We argue that the establishment of this new climate regime is related to an upward trend throughout the whole of the 20th century in the cross-correlation between the NAO index and Rogers' first storm activity mode for the North Atlantic.