Ecological regime shifts are abrupt changes in the structure and function of ecosystems that persist over time, but evidence of contemporary regime shifts are rare. Historical scale data from 52,384 individual wild Atlantic salmon caught in 180 rivers from 1989 to 2017 reveal that growth of Atlantic salmon across the Northeast Atlantic Ocean abruptly decreased following the year 2004. At the same time, the proportion of early maturing Atlantic salmon decreased. These changes occurred after a marked decrease in the extent of Arctic water in the Norwegian Sea, a subsequent warming of spring water temperature before Atlantic salmon entering the sea, and an approximately 50% reduction of zooplankton across large geographic areas of the Northeast Atlantic Ocean. A sudden decrease in growth was also observed among Atlantic mackerel in the Norwegian Sea. Our results point toward an ecosystem-scale regime shift in the Northeast Atlantic Ocean.