Recovery of overexploited marine populations has been slow, and most remain below target biomass levels. Using a global meta-analysis of overfished stocks, a NCEAS Working Group finds that resilience of those stocks subjected to moderate levels of overfishing is enhanced, not compromised, offering the possibility of swift recovery. However, prolonged intense overexploitation, especially for collapsed stocks, not only delays rebuilding but also substantially increases the uncertainty in recovery times, despite predictable influences of fishing and life history. Timely and decisive reductions in harvest rates could mitigate this uncertainty. Instead, current harvest and low biomass levels render recovery improbable for the majority of the world’s depleted stocks.