Abstract: Prior studies of the long-term temperature record in the Southeastern United States (SE US) mostly discuss the long-term cooling trend, and the inter-annual variability produced by the region's strong ties to El Niño Southern Oscillation (ENSO). An examination of long-term temperature records in the SE US show clear multi-decadal variations in temperature, with relative warm periods in the 1920's through the mid 1950's and a cool period in the late 1950's through the late 1990's. This substantial shift in multi-decadal variability is not well understood and has not been fully investigated. It appears to account for the long-term downward trend in temperatures. An accurate characterization of this variability could lead to improved interannual and long-term forecasts, which would be useful for agricultural planning, drought mitigation, water management, and preparation for extreme temperature events. Statistical methods are employed to determine the spatial coherence of the observed variability on seasonal time scales. The goal of this study is to characterize the nature of this variability through the analysis of National Weather Service Cooperative Observer Program (COOP) station data in Florida, Georgia, Alabama, North Carolina, and South Carolina. One finding is a shift in the temperature Probability Distribution Function (PDF) between warm regimes and cool regimes.