Analyses of global climate from measurements dating back to the nineteenth century show an 'Atlantic Multidecadal Oscillation' (AMO) as a leading large-scale pattern of multidecadal variability in surface temperature. Yet it is not possible to determine whether these fluctuations are genuinely oscillatory from the relatively short observational record alone. Using a 1400 year climate model calculation, we are able to simulate the observed pattern and amplitude of the AMO. The results imply the AMO is a genuine quasi-periodic cycle of internal climate variability persisting for many centuries, and is related to variability in the oceanic thermohaline circulation (THC). This relationship suggests we can attempt to reconstruct past THC changes, and we infer an increase in THC strength over the last 25 years. Potential predictability associated with the mode implies natural THC and AMO decreases over the next few decades independent of anthropogenic climate change.