Cold-water corals (CWCs) are the engineers of complex ecosystems forming unique biodiversity hotspots in the deep sea. They are expected to suffer dramatically from future environmental changes in the oceans such as ocean warming, food depletion, deoxygenation, and acidification. However, over the last decades of intense deep-sea research, no extinction event of a CWC ecosystem is documented, leaving quite some uncertainty on their sensitivity to these environmental parameters. Paleoceanographic reconstructions offer the opportunity to align the on- and offsets of CWC proliferation to environmental parameters. Here, we present the synthesis of 6 case studies from the North Atlantic Ocean and the Mediterranean Sea, revealing that food supply controlled by export production and turbulent hydrodynamics at the seabed exerted the strongest impact on coral vitality during the past 20,000 years, whereas locally low oxygen concentrations in the bottom water can act as an additional relevant stressor. The fate of CWCs in a changing ocean will largely depend on how these oceanographic processes will be modulated. Future ocean deoxygenation may be compensated regionally where the food delivery and food quality are optimal.