European climate is heavily influenced by the North Atlantic Oscillation (NAO). However, the spatial structure of the NAO is varying with time, affecting its regional importance. By analyzing an 850-year global climate model simulation of the last millennium it is shown that the variations in the spatial structure of the NAO can be linked to the Atlantic Multidecadal Oscillation (AMO). The AMO changes the zonal position of the NAO centers of action, moving them closer to Europe or North America. During AMO+ states, the Icelandic Low moves further towards North America while the Azores High moves further towards Europe and vice versa for AMO- states. The results of a regional downscaling for the East Atlantic/European domain show that AMO-induced changes in the spatial structure of the NAO reduce or enhance its influence on regional climate variables of the Baltic Sea such as sea surface temperature, ice extent, or river runoff.