One of the twenty-first century’s greatest environmental challenges is to recover and restore species, habitats and ecosystems. The decision about how to initiate restoration is best-informed by an understanding of the linkages between ecosystem components and, given these linkages, an appreciation of the consequences of choosing to recover one ecosystem component before another. However, it remains difficult to predict how the sequence of species’ recoveries within food webs influences the speed and trajectory of restoration, and what that means for human well-being. Here, we develop theory to consider the ecological and social implications of synchronous versus sequential (species-by-species) recovery in the context of exploited food webs. A dynamical systems model demonstrates that synchronous recovery of predators and prey is almost always more efficient than sequential recovery. Compared with sequential recovery, synchronous recovery can be twice as fast and produce transient fluctuations of much lower amplitude. A predator-first strategy is particularly slow because it counterproductively suppresses prey recovery. An analysis of real-world predator–prey recoveries shows that synchronous and sequential recoveries are similarly common, suggesting that current practices are not ideal. We highlight policy tools that can facilitate swift and steady recovery of ecosystem structure, function and associated services.