This work investigates links between Arctic surface variability and the phases of the winter (DJF) North Atlantic Oscillation (NAO) on interannual time-scales. The analysis is based on ERA-reanalysis and model data from the EC-Earth global climate model. Our study emphasizes a mode of sea-ice cover variability that leads the NAO index by 1 year. The mechanism of this leading is based on persistent surface forcing by quasi-stationary meridional thermal gradients. Associated thermal winds lead a slow adjustment of the pressure in the following winter, which in turn feeds-back on the propagation of sea-ice anomalies. The pattern of the sea-ice mode leading NAO has positive anomalies over key areas of South-Davis Strait-Labrador Sea, the Barents Sea and the Laptev-Ohkostsk seas, associated to a high pressure anomaly over the Canadian Archipelago-Baffin Bay and the Laptev-East-Siberian seas. These anomalies create a quasi-annular, quasi-steady, positive gradient of sea-ice anomalies about coastal line (when leading the positive NAO phase) and force a cyclonic vorticity anomaly over the Arctic in the following winter. During recent decades in spite of slight shifts in the modes’ spectral properties, the same leading mechanism remains valid. Encouraging, actual models appear to reproduce the same mechanism leading model’s NAO, relative to model areas of persistent surface forcing. This indicates that the link between sea-ice and NAO could be exploited as a potential skill-source for multi-year prediction by addressing the key problem of initializing the phase of the NAO/AO (Arctic Oscillation).