Understanding the internal ocean variability and its influence on climate is imperative for society. A key aspect concerns the enigmatic Atlantic Multidecadal Oscillation (AMO), a feature defined by a 60- to 90-year variability in North Atlantic sea-surface temperatures. The nature and origin of the AMO is uncertain, and it remains unknown whether it represents a persistent periodic driver in the climate system, or merely a transient feature. Here, we show that distinct, ∼55- to 70-year oscillations characterized the North Atlantic ocean-atmosphere variability over the past 8,000 years. We test and reject the hypothesis that this climate oscillation was directly forced by periodic changes in solar activity. We therefore conjecture that a quasi-persistent ∼55- to 70-year AMO, linked to internal ocean-atmosphere variability, existed during large parts of the Holocene. Our analyses further suggest that the coupling from the AMO to regional climate conditions was modulated by orbitally induced shifts in large-scale ocean-atmosphere circulation.