Rapid changes in North Atlantic climate over the last millennia were driven by coupled sea surface/atmospheric processes and rates of deep-water formation. Holocene climate changes, however, remain poorly documented due to a lack of high-resolution paleoclimate records, and their impacts on marine ecosystems remain unknown. We present a 4500 years absolute-dated sea surface radiocarbon record from northeast Atlantic cold-water corals. In contrast to the current view that surface ocean changes occurred on millennial-scale cycles, our record shows more abrupt changes in surface circulation. Changes were centered at 3.4, 2.7, 1.7 and 1.2 ky BP, and associated with atmospheric re-organization. Solar irradiance may have influenced these anomalies, but changes in North Atlantic deep-water convection are likely to have amplified these signals. Critically, we provide the first evidence that these perturbations in Atlantic Meridional Overturning Circulation led to the decline of cold-water coral ecosystems from 1.2 to ~ 0.1 ky BP.