Hypoxia has occurred intermittently in the Baltic Sea since the establishment of brackish-water conditions at ~8000 years B.P., principally as recurrent hypoxic events during the Holocene Thermal Maximum (HTM) and the Medieval Climate Anomaly (MCA). Sedimentary phosphorus release has been implicated as a key driver of these events, but previous paleoenvironmental reconstructions have lacked the sampling resolution to investigate feedbacks in past iron-phosphorus cycling on short timescales. Here we employ Laser Ablation (LA)-ICP-MS scanning of sediment cores to generate ultra-high resolution geochemical records of past hypoxic events. We show that in-phase multidecadal oscillations in hypoxia intensity and iron-phosphorus cycling occurred throughout these events. Using a simple box model, we demonstrate that such oscillations were likely driven by instabilities in the dynamics of iron-phosphorus cycling under pre-industrial phosphorus loads, and modulated by external climate forcing. Oscillatory behavior could complicate the recovery from hypoxia during future trajectories of external loading reductions.