A 17 000 yr fire history from Yellowstone National Park demonstrates a strong link between changes in climate and variations in fire frequency on millennial time scales. The fire history reconstruction is based on a detailed charcoal stratigraphy from Cygnet Lake in the rhyolite plateau region. Macroscopic charcoal particles were tallied from contiguous 1 cm samples of a 6.69-m-long core, and the data were converted to charcoal-accumulation rates at evenly spaced time intervals. Intervals of high charcoal-accumulation rates were interpreted as local fire events on the basis of information obtained from modern charcoal-calibration studies in the Yellowstone region. The record indicates that fire frequency was moderate (4 fires/1000 yr) during the late glacial period, reached highest values in the early Holocene (>10 fires/1000 yr), and decreased after 7000 calendar yr B.P. The present fire regime (2–3 fires/1000 yr) was established in the past 2000 yr. The charcoal stratigraphy correlates well with variations in July insolation through time, which suggests that regional climate changes are responsible for the long-term variations in fire frequency. In the early Holocene, summer insolation was near its maximum, which resulted in warmer, effectively drier conditions throughout the northwestern United States. At this time, the fire frequency near Cygnet Lake was at its highest. After 7000 calendar yr B.P., summer insolation decreased to present values, the regional climate became cooler and wetter, and fires were less frequent. The Cygnet Lake record suggests that long-term fire frequencies have varied continuously with climate change, even when the vegetation has remained constant.