Interannual to inter-decadal variability in Atlantic hurricane activity has been well-documented from the historical hurricane dataset of the past 100 years. However, the instrumental record is too short to reveal any possible variability occurring at the century to millennial timescales. By studying the overwash deposits preserved in the sediments of coastal lakes and marshes, we have produced millennial proxy records of catastrophic hurricane landfalls from a dozen sites from Texas to the Florida Panhandle. A 7,000-year sedimentary record from Western Lake, NW Florida, shows that few catastrophic hurricane landfalls occurred during 5000-3400 yr BP and during the last 1400 years, but the landfall frequency increased dramatically during 3400-1400 yr BP. The "hyperactive" millennia of 3400-1400 yr BP were probably caused by a southwestward shift of the Bermuda High, which steered more hurricanes towards the Gulf of Mexico coast instead of the Atlantic coast. Similar patterns of millennial-scale variability were also found in the proxy records from the Pearl River Marsh (Louisiana), Pascagoula Marsh (Mississippi), Lake Shelby (Alabama), and Camp Creek Lake (NW Florida). A long-term (multi-millennial) record is necessary to understand the full range of natural variability in hurricane activities, because the present millennium is a relatively quiescent period during the Holocene in terms of catastrophic hurricane landfalls along the Gulf Coast.