For the purpose of detecting the effects of human activities on climate change, it is important to document natural change in past climate. In this context, it has proved particularly difficult to study the variability in the occurrence of extreme climate events, such as storms with exceptional rainfall. Previous investigations have established storm chronologies using sediment cores from single lakes, but such studies can be susceptible to local environmental bias. Here we date terrigenous inwash layers in cores from 13 lakes, which show that the frequency of storm-related floods in the northeastern United States has varied in regular cycles during the past 13,000 years (13 kyr), with a characteristic period of about 3 kyr. Our data show four peaks in storminess during the past 14 kyr, approximately 2.6, 5.8, 9.1 and 11.9 kyr ago. This pattern is consistent with long-term changes in the average sign of the Arctic Oscillation, suggesting that modulation of this dominant atmospheric mode may account for a significant fraction of Holocene climate variability in North America and Europe.