The Red Sea hosts a deep marine environment unique among the world’s oceans. It is occupied, almost homogeneously from the subsurface (~137 to 300 m) to depths over 2000 m, by a warm (~21.5°C) and highly saline (~40.5) water mass, referred to as the Red Sea Deep Water (RSDW). Previous studies suggested that the RSDW is mainly ventilated, continuously or intermittently, by dense outflows from the northern Gulfs of Suez and Aqaba with a resulting sluggish renewal time on the order of 36 to 90 years. We use six repeated hydrographic observations spanning the period 1982–2011 and simulations of an ocean general circulation model with realistic atmospheric forcing to show that large portions of the RSDW were episodically replaced during 1982–2001 by new dense waters mainly formed by open-ocean deep convections in the northern Red Sea during anomalously cold winters, pointing to a much shorter renewal time for the RSDW on the order of a decade. We further show that the winter cooling anomaly in the Red Sea region was a part of a large-scale climate variability pattern associated with either large volcanic eruptions or the North Atlantic Oscillation (NAO). Consequently, significant deep water formation events occurred in the Red Sea in the winters following the 1982 El Chichón eruption in Mexico and the 1991 Mount Pinatubo eruption in the Philippines and during the strong positive phase of the NAO in the winter of 1989