The Greater Yellowstone Ecosystem (GYE), a mountainous region in western North America and home to Yellowstone National Park, is one of the last remaining, nearly intact landscapes in the mid-latitudes. In the summer of 1988, dry conditions led to large fires across 36% of the Park. That single year comprised the largest fire-fighting effort in the US at the time and cost over US$ 120 million. Since then, the western US has experienced more large, severe fires with costs now exceeding $2 billion per year. Are current fires unprecedented? Paleoecological data spanning the last 15,000 years allow us to compare recent events with the long-term variability of fire and assess both the drivers of past fires and their consequences on the landscape. Charcoal data from a network of seven sites in the GYE suggest that periods of high fire activity have occurred during times of high temperatures and pronounced drought, such as in the early Holocene and the Medieval Climate Anomaly. Fire thus emerges as a natural component of the GYE greatly dependent on changing vegetation, climate and weather conditions. Calibrated vegetation reconstructions show that, although no single fire has triggered long-term transformation of vegetation composition in the past, shifts in the fire regime coupled with climate variability have led to a spatial reorganization of vegetation, particularly at lower treeline. Recent fires in the GYE, which were seemingly unprecedented in terms of magnitude and impact, can be reinterpreted as the expected outcome of ecosystem dynamics when millennial time scales are considered. The longer perspective highlights the divergence of the societal and ecological definitions of ‘novel' and ‘surprise', with implications for conservation strategies in the future.