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. Instead, the ecosystem regenerates towards a new ecological baseline. This new baseline is characterized by lower and more variable biomass of cod, the commercially most important fish stock in the Baltic Sea, even under very low exploitation pressure.