The North Atlantic Oscillation (NAO) is an important driver of year-to-year weather variability in Europe and North America, but its behavior on longer timescales is disputed. We present a new reconstruction of the NAO over the last millennium using water isotope proxy data from ice cores, speleothems, trees, and other archives. We find pronounced but irregular multidecadal to centennial variability. Better accounting for such variability in climate models is crucial to better project future climate.