Millennial-scale records of forest fire provide important baseline information for ecosystem management, especially in regions with too few recent fires to describe the historical range of variability. Charcoal records from lake sediments and soil profiles are well suited for reconstructing the incidence of past fire and its relationship to changing climate and vegetation. We highlight several records from western North America and their relevance in reconstructing historical forest dynamics, fire-climate relationships, and feedbacks between vegetation and fire under climate change. Climatic effects on fire regimes are evident in many regions, but comparisons of paleo-fire records sometimes show a lack of synchrony, indicating that local factors substantially affect fire occurrence, even over long periods. Furthermore, the specific impacts of vegetation change on fire regimes vary among regions with different vegetation histories. By documenting the effects on fire patterns of major changes in climate and vegetation, paleo-fire records can be used to test the mechanistic models required for the prediction of future variations in fire.