We force the GCM with anomalous surface heat fluxes similar to those occurring in fall and winter in the Barents-Kara Sea, where strong air-sea gradients lead to strong surface fluxes. We carried out systemic ensemble simulations to determine the atmospheric response to such perturbations and investigate the mechanisms causing it. We found that a transient warming of the polar surface triggers anomalous deep convection and eventually, on timescales of tens of days, leads to circulation changes in the lower stratosphere. These stratospheric changes persist over several months and can, in turn, lead to robust midlatitude weather anomalies two months after the polar surface perturbation ceased—consistent with recent observational analyses. Moreover, anomalies can also be induced in middle and higher latitudes of the opposite hemisphere, pointing to possible interhemispheric teleconnections. The stratospheric anomalies and their delayed feedback onto the troposphere are mediated by changes in the generation and propagation characteristics of Rossby waves, which we elucidate through analyses of Eliassen-Palm fluxes and the residual circulation. The relevance of the mechanisms we identify for Earth's atmosphere will be discussed.