Overfishing of large predatory fish populations has resulted in lasting restructurings of entire marine food webs worldwide, with serious socio-economic consequences. Fortunately, some degraded ecosystems show signs of recovery. A key challenge for ecosystem management is to anticipate the degree to which recovery is possible. By applying a statistical food-web model, using the Baltic Sea as a case study, we show that under current temperature and salinity conditions, complete recovery of this heavily altered ecosystem will be impossible.