Although the expectation of lack of resilience of seamount vulnerable marine ecosystems has become a paradigm in seamount ecology and a tenet of fisheries management, recovery has not been tested on time scales >10 years. The Northwestern Hawaiian Ridge and Emperor Seamounts have experienced the highest documented fish and invertebrate seamount fisheries takes in the world. Surveys show that, despite visible evidence of substantial historic fishing pressure, a subset of these seamounts that have been protected for >30 years showed multiple signs of recovery including corals regrowing from fragments and higher abundances of benthic megafauna than Still Trawled sites. Contrary to expectations, these results show that, with long-term protection, some recovery of seamount deep-sea coral communities may be possible on 30- to 40-year time scales. The current practice of allowing continued bottom-contact fishing at heavy trawled sites may cause damage to remnant populations, which likely play a critical role in recovery.