In recent years, many components of the connection between Eurasian autumn snow cover and wintertime North Atlantic Oscillation (NAO) have been investigated, suggesting that November snow cover distribution has strong prediction power for the upcoming Northern Hemisphere winter climate. However, the non-stationarity of this relationship could impact its use for prediction routines. Here we use snow products from long-term reanalyses to investigate interannual and interdecadal links between autumnal snow cover and atmospheric conditions in winter. We find evidence for a negative NAO-like signal after November with a strong west-to-east snow cover gradient, which is valid throughout the last 150 years. This correlation is consistently linked to a weak stratospheric polar vortex state. Nevertheless, decadal evolution of this link shows episodes of decreased correlation strength, which co-occur with episodes of low variability in the November snow index. By contrast, periods with high prediction skill for winter NAO are found in periods of high November snow variability, which co-occur with the Arctic warming periods of the 20th century, namely the early 20th-century Arctic warming between 1920 and 1940 and the ongoing anthropogenic global warming at the end of the 20th century. A strong snow dipole itself is consistently associated with reduced Barents–Kara sea ice concentration, increased Ural blocking frequency and negative temperature anomalies in eastern Eurasia.