The Arctic polar vortex exhibited widespread regions of low temperatures during the winter of 2005, resulting in significant ozone depletion by chlorine and bromine species. We show that chemical loss of column ozone (deltaO3) and the volume of Arctic vortex air cold enough to support the existence of polar stratospheric clouds (V_PSC) both exceed levels found for any other Arctic winter during the past 40 years. Cold conditions and ozone loss in the lowermost Arctic stratosphere (e.g., between potential temperatures of 360 to 400 K) were particularly unusual compared to previous years. Measurements indicate DO3 = 121 ± 20 DU and that deltaO3 versus V_PSC lies along an extension of the compact, near linear relation observed for previous Arctic winters. The maximum value of V_PSC during five to ten year intervals exhibits a steady, monotonic increase over the past four decades, indicating that the coldest Arctic winters have become significantly colder, and hence are more conducive to ozone depletion by anthropogenic halogens.