Limiting climate warming below 2°C requires both reducing anthropic greenhouse gas emissions and sequestering more atmospheric carbon. Natural Climate Solutions (NCS) rely on the ability of ecosystems to capture and store carbon. Despite the important role of marine megafauna on the ocean carbon cycle, its potential as a NCS has not yet been explored. Here, we quantify the amount of carbon potentially sequestered by five baleen whale species across the Southern Hemisphere between 1890 and 2100 through both the sinking of carcasses after natural death and the fertilisation of phytoplankton by nutrients in faeces. At their pre-exploitation abundances, the five whales could sequester 10.6 106 tonnes of carbon per year (tC.yr-1) but this natural carbon sink was reduced at 2 106 tC.yr-1 in 1965 due to commercial whaling. However, the restoration of whale populations could sequester 8.7 106 tC.yr-1 at the end of the 21st century suggesting an efficient but neglected NCS that remains to be estimated globally including all marine vertebrates.