Current and future prospects for successfully rebuilding global fisheries remain debated due to uncertain stock status, variable management success, and disruptive environmental change. While scientists routinely account for some of this uncertainty in population models, the mechanisms by which this translates into decision-making and policy are problematic and can lead to unintentional overexploitation. Here, we explicitly track the role of measurement uncertainty and environmental variation in the decision-making process for setting catch quotas. Analyzing 109 well-sampled stocks from all oceans, we show that current practices may attain 55% recovery on average, while richer decision methods borrowed from robotics yield 85% recovery of global stocks by midcentury, higher economic returns, and greater robustness to environmental surprises. These results challenge the consensus that global fisheries can be rebuilt by existing approaches alone, while also underscoring that rebuilding stocks may still be achieved by improved decision-making tools that optimally manage this uncertainty.