The Barents Sea attracts year-around human activity as the winter sea ice cover retreats, creating a need for short and long term prediction of environmental conditions in the region. Previous studies have shown that local ocean heat content and heat transport at the Barents Sea Opening provide interannual to decadal predictability of Barents Sea ice cover. Part of this predictability is suggested to originate from thermodynamic anomalies propagating along the Norwegian Atlantic Current. To better understand this source of predictability, and the relevant timescales, we use models (Coupled Model Intercomparison Project Phase 6; CMIP6) and satellite observations, to study the linear response of the monthly mean Barents Sea ice cover to downstream sea surface temperature anomalies. We show that in March the sea ice response is strongest on short lead times (<2 year), vanishing towards ~7 year timescale and that the linear sea ice response function can be reconstructed using an advective-diffusive ‘leaky-pipe’ model with multiple propagation timescales. The sea surface temperature based sea ice predictability is linked to decadal and longer timescale variability. Our results also show that sea surface temperatures close to the sea ice edge provide the best predictability at short timescales, but with a skill that approaches that of the sea surface temperatures further away at long timescales.