Satellite-derived sea ice concentration (SIC) and reanalyzed atmospheric data are used to explore the predictability of the winter Euro-Atlantic climate resulting from autumn SIC variability over the Barents–Kara Seas region (SIC/BK). The period of study is 1979/80–2012/13. Maximum covariance analyses show that the leading predictand is indistinguishable from the North Atlantic Oscillation (NAO). The leading covariability mode between September SIC/BK and winter North Atlantic–European sea level pressure (SLP) is not significant, indicating that no empirical prediction skill can be achieved. The leading covariability mode with either October or November SIC/BK is moderately significant (significance levels <10%), and both predictor fields yield a cross-validated NAO correlation of 0.3, suggesting some empirical prediction skill of the winter NAO index, with sea ice reduction in the Barents–Kara Seas being accompanied by a negative NAO phase in winter. However, only November SIC/BK provides significant cross-validated skill of winter SLP, surface air temperature, and precipitation anomalies over the Euro-Atlantic sector, namely in southwestern Europe. Statistical analysis suggests that November SIC/BK anomalies are associated with a Rossby wave train–like anomaly across Eurasia that affects vertical wave activity modulating the stratospheric vortex strength, which is then followed by downward propagation of anomalies that impact transient-eddy activity in the upper troposphere, helping to settle and maintain the NAO-like pattern at surface. This stratospheric pathway is not detected when using October SIC/BK anomalies. Hence, only November SIC/BK, with a one-month lead time, could be considered as a potential source of regional predictability.