We report the first empirical quantification of the relation between winter-spring loss of Arctic ozone and changes in stratospheric climate. Our observations show that ~15 DU additional loss of column ozone can be expected per Kelvin cooling of the Arctic lower stratosphere, an impact nearly three times larger than current model simulations suggest. We show that stratospheric climate conditions became significantly more favorable for large Arctic ozone losses over the past four decades; i.e., the maximum potential for formation of polar stratospheric clouds increased steadily by a factor of three. Severe Arctic ozone loss during the past decade occurred as a result of the combined effect of this long-term climate change and the anthropogenic increase in stratospheric halogens.