Precautionary management for fish stocks in need of recovery requires that likely stock increases can be distinguished from model artefacts and that the uncertainty of stock status can be handled. Yet, ICES stock assessments are predominantly deterministic and many EC management plans are designed for deterministic advice. Using the eastern Baltic cod (Gadus morhua) stock as an example, we show how deterministic scientific advice can lead to illusive certainty of a rapid stock recovery and management decisions taken in unawareness of large uncertainties in stock status. By (i) performing sensitivity analyses of key assessment model assumptions, (ii) quantifying the uncertainty of the estimates due to data uncertainty, and (iii) developing alternative stock and ecosystem indicators, we demonstrate that estimates of recent fishing mortality and recruitment of this stock were highly uncertain and show that these uncertainties are crucial when combined with management plans based on fixed reference points of fishing mortality. We therefore call for fisheries management that does not neglect uncertainty. To this end, we outline a four-step approach to handle uncertainty of stock status in advice and management. We argue that it is time to use these four steps towards an ecosystem-based approach to fisheries management.