Cold-water coral (CWC) habitats dwell on continental shelves, slopes, seamounts, and ridge systems around the world’s oceans from 50 to 4000 m depth, providing heterogeneous habitats which support a myriad of associated fauna. These highly diverse ecosystems are threatened by human stressors such as fishing activities, gas and oil exploitation, and climate change. Since their life-history traits such as long lifespan and slow growth rates make CWCs very vulnerable to potential threats, it is a foremost challenge to explore the viability of restoration actions to enhance and speed up their recovery. In contrast to terrestrial and shallow-water marine ecosystems, ecological restoration in deep marine environments has received minimal attention. This review, by means of a systematic literature search, aims to identify CWC restoration challenges, assess the most suitable techniques to restore them, and discuss future perspectives. Outcomes from the few restoration actions performed to date on CWCs, which have lasted between 1 to 4 years, provide evidence of the feasibility of coral transplantation and artificial reef deployments. Scientific efforts should focus on testing novel and creative restoration techniques, especially to scale up to the spatial and temporal scales of impacts. There is still a general lack of knowledge about the biological, ecological and habitat characteristics of CWC species exploration of which would aid the development of effective restoration measures. To ensure the long-term viability and success of any restoration action it is essential to include holistic and long-term monitoring programs, and to ideally combine active restoration with natural spontaneous regeneration (i.e., passive restoration) strategies such as the implementation of deep-sea marine protected areas (MPAs). We conclude that a combination of passive and active restoration approaches with involvement of local society would be the best optimal option to achieve and ensure CWC restoration success.