We examine the seasonal predictability of the winter (December--January--February) North Atlantic Oscillation (NAO) from lagged north Atlantic sea surface temperatures (SSTs) for the period 1950/1--2000/1. We identify two lagged modes of SST variability whose principal components (PCs) are correlated significantly to upcoming winter NAO indices. We use linear regression with the PCs as predictors to assess the predictability of the winter NAO from cross-validation over the full period and from replicated real-time forecasts over the recent 15 year period 1986/7--2000/1. The model anticipates, in early November, the upcoming winter NAO - for a range of NAO indices - with a correlation between 0.47 and 0.63 for 1950/1--2000/1, and between 0.51 and 0.65 for the replicated real-time forecast period. The model also anticipates the correct NAO sign in 67% to 75% of the last 51 winters and in 80% to 93% of the last 15 winters.