A comparison of a Mg/Ca-based sea-surface temperature (SST)-anomaly record from the northern Gulf of Mexico, a calculated index of variability in observed North Atlantic SST known as the Atlantic Multidecadal Oscillation (AMO), and a tree-ring reconstruction of the AMO contain similar patterns of variation over the last 110 years. Thus, the multidecadal variability observed in the instrumental record is present in the tree-ring and Mg/Ca proxy data. Frequency analysis of the Gulf of Mexico SST record and the tree-ring AMO reconstruction from 1550 to 1990 found similar multidecadal-scale periodicities (~30–60 years). This multidecadal periodicity is about half the observed (60–80 years) variability identified in the AMO for the 20th century. The historical records of hurricane landfalls reveal increased landfalls in the Gulf Coast region during time intervals when the AMO index is positive (warmer SST), and decreased landfalls when the AMO index is negative (cooler SST). Thus, we conclude that alternating intervals of high and low hurricane landfall occurrences may continue on multidecadal timescales along the northern Gulf Coast. However, given the short length of the instrumental record, the actual frequency and stability of the AMO are uncertain, and additional AMO proxy records are needed to establish the character of multidecadal-scale SST variability in the North Atlantic.