The North Atlantic Oscillation (NAO) is one of the main modes of climate variability and the dominant mode of large-scale atmospheric variability in the North Atlantic basin and has large impacts on the European climate, yet the behaviour of NAO in the future remains uncertain. Here we assess the NAO response in the past and in a warming climate by looking at a comprehensive set of coupled model simulations performed by the Paleoclimate Model Intercomparison Project (PMIP) and the Coupled Model Intercomparison Project (CMIP) for four experiments: the mid-Holocene (6 ka; midHolocene), the Last Glacial Maximum (21 ka; lgm), the Last Interglacial (127 ka; lig127k) and an idealised greenhouse gas (GHG)-forced experiment from the CMIP DECK with abrupt quadrupled CO2 (abrupt4xCO2). Although there are various setups across experiments, the midHolocene and lig127k are mainly characterised by altered orbital configurations, inducing variations in the seasonal cycle and redistributing energy across latitudes. The lgm and abrupt4xCO2 are characterised by GHG forcings that induce substantial global temperature change, and the lgm includes large ice sheets that alter the storm-tracks. Our results show that the NAO alters in these latter two experiments, but is not sensitive to the orbital configurations. NAO weakens in response to cooling and strengthens as a result of warming. The associated teleconnections change consistently with the theory and are sensitive to the change in NAO amplitude. The two orbital experiments do not show a clear change in associated temperature and precipitation. The weakened NAO in the lgm is associated with a cooler and drier northern Europe, while the enhanced NAO in the abrupt4xCO2 causes a warmer and wetter northern Europe as compared to the piControl. No clear relationship is found in the ENSO-NAO teleconnection.