Ensemble experiments with a coupled atmosphere-ocean model show that natural variations in the strength of ocean thermohaline circulation (THC), a key player in the maintenance of the climate of Earth, are potentially predictable one to two decades into the future. In contrast to previous studies, these predictable THC variations lead to predictable variations of the climate of Western Europe that could be of considerable benefit to society. Further model experiments also show that, under certain conditions, variations in the strength of the THC may even be predictable for more than 50 years into the future.