Human-caused forest transitions are documented worldwide, especially during periods when land use by dense agriculturally-based populations intensified. However, the rate at which prehistoric human activities led to permanent deforestation is poorly resolved. In the South Island, New Zealand, the arrival of Polynesians c. 750 years ago resulted in dramatic forest loss and conversion of nearly half of native forests to open vegetation. This transformation, termed the Initial Burning Period, is documented in pollen and charcoal records, but its speed has been poorly constrained. High-resolution chronologies developed with a series of AMS radiocarbon dates from two lake sediment cores suggest the shift from forest to shrubland occurred within decades rather than centuries at drier sites. We examine two sites representing extreme examples of the magnitude of human impacts: a drier site that was inherently more vulnerable to human-set fires and a wetter, less burnable site. The astonishing rate of deforestation at the hands of small transient populations resulted from the intrinsic vulnerability of the native flora to fire and from positive feedbacks in post-fire vegetation recovery that increased landscape flammability. Spatially targeting burning in highly-flammable seral vegetation in forests rarely experiencing fire was sufficient to create an alternate fire-prone stable state. The New Zealand example illustrates how seemingly stable forest ecosystems can experience rapid and permanent conversions. Forest loss in New Zealand is among the fastest ecological transitions documented in the Holocene; yet equally rapid transitions can be expected in present-day regions wherever positive feedbacks support alternate fire-inhibiting, fire-prone stable states.