The North Atlantic Oscillation is the dominant atmospheric pressure mode in the North Atlantic region and affects winter temperature and precipitation in the Mediterranean, northwest Europe, Greenland, and Asia1. The index1 that describes the sea-level pressure difference between Iceland and the Azores is correlated with a dipole precipitation pattern over northwest Europe and northwest Africa. How the North Atlantic Oscillation will develop as the Greenland ice sheet melts is unclear2. A potential past analogue is the early Holocene, during which melting ice sheets around the North Atlantic3, 4 freshened surface waters, affecting the strength of the meridional overturning circulation5. Here we present a Holocene rainfall record from northwest Africa based on speleothem δ18O and compare it against a speleothem-based rainfall record from Europe6. The two records are positively correlated during the early Holocene, followed by a shift to an anti-correlation, similar to the modern record, during the mid-Holocene. On the basis of our simulations with an Earth system model, we suggest the shift to the anti-correlation reflects a large-scale atmospheric and oceanic reorganization in response to the demise of the Laurentide ice sheet and a strong reduction of meltwater flux to the North Atlantic, pointing to a potential sensitivity of the North Atlantic Oscillation to the melting of ice sheets.