One of the longest marine monitoring programs in the North Sea has been the spatiotemporal surveying of subsurface plankton since 1931. During this period a regime shift was detected in the late 1980s culminating in marked changes in phytoplankton, zooplankton and in the fisheries of horse mackerel. Here we used the phytoplankton colour index, a visual biomass estimate, from 1948 to 2010 and total diatom abundance from 1958 to 2010 to test whether the well-documented regime shift could have been anticipated by the recently developed Early-Warning Signals for critical transitions (EWS). We estimated EWS, namely autocorrelation and standard deviation, within moving windows along the time series prior to the regime shift. We found that both statistics increased revealing that the North Sea ecosystem was becoming progressively unstable prior to the regime shift. Moreover, this high-resolution time series permitted us to test for robustness, error and significance of the EWS. We did that by dividing the time series into independent blocks and estimating EWS after bootstrapping and randomising the blocks. This alternative approach confirmed the robustness of the EWS with limited associated errors. In particular, we found that the warning was significantly evident years before the onset of the regime shift. We conclude that EWS may provide robust and timely warning for upcoming regime shifts depending on the quality and quantity of recorded data in marine ecosystems.