During past glacial periods, extensive areas of North America were covered by permafrost. The timing and extent of these paleo-permafrost conditions, however, remains ambiguous. Here we present a 250,000-year record of speleothem growth from a midlatitude North American cave and report 141 U-Th ages with hiatuses in growth that reflect the development of temporally continuous permafrost. Combined with U-Th ages from other speleothem studies, we demonstrate that regional permafrost conditions occurred during both of the prior two glacial maxima but were markedly shorter in duration during the penultimate (Marine Isotope Stage 6, MIS 6) versus the last (MIS 2) glacial period. Notably, a network of sea surface temperatures indicates that mid- and low-latitude temperatures were 0.9 °C ± 0.2 °C warmer during the culmination of MIS 6 versus MIS 2. Our results illustrate the importance of developing regional paleo-permafrost records and highlight the sensitivity of permafrost conditions during glacial periods to relatively small differences in global-scale temperature.