While the Arctic's accelerated warming and sea ice decline have been associated with Eurasian cooling, debates persist between those attributing this to sea ice retreat and those to internal variability. Our study examines the association between autumn sea ice variability over the Barents-Kara Seas and extreme cold winters in Europe. Using the observational data and composite analysis, we explore the interannual variability and the potential linkage between sea ice and atmospheric circulation patterns. It reveals a correlation with shifts toward a negative phase of North Atlantic Oscillation and more frequent episodes of the atmospheric blocking over Greenland and the North Atlantic. Furthermore, the negative phase of the North Atlantic Oscillation and enhanced blocking are closely related and mutually reinforcing, shaping the spatial distribution of cold anomalies over much of the European continent. Our results suggest a link between the unusual decrease in Barents-Kara Sea ice during autumn and the occurrence of intense European weather extremes in subsequent winter months, emphasizing the need for delving deeper into this relationship on monthly time scales to enhance our predictive capabilities for midlatitude extreme events.