Predicting fish stock variations on interannual to decadal time scales is one of the major issues in fisheries science and management. Although the field of marine ecological predictions is still in its infancy, it is understood that a major source of multi-year predictability resides in the ocean. Here we show the first highly skilful long-term predictions of the commercially valuable Barents Sea cod stock. The 7-year predictions are based on the propagation of ocean temperature anomalies from the subpolar North Atlantic toward the Barents Sea, and the strong co-variability between these temperature anomalies and the cod stock. Retrospective predictions for the period 1957-2017 capture well multi-year to decadal variations in cod stock biomass, with cross-validated explained variance of over 60%. For lead times longer than one year the statistical long-term predictions show more skill than operational short-term predictions used in fisheries management and lagged persistence forecasts. Our results thus demonstrate the potential for ecosystem-based fisheries management, which could enable strategic planning on longer time scales. Future predictions show a gradual decline in the cod stock towards 2024.