Prior to the industrial era, human-caused land cover change at large scales was closely linked to the development of densely populated agricultural societies. This was the case in Eastern Polynesia where colonization of islands by agricultural-based societies led to extensive clearing of native vegetation to facilitate cultivation of introduced crops. Similarly, Polynesian (M?ori) arrival in the South Island of New Zealand at ca. 1280 A.D. was followed by conversion of nearly half of the native forests to open scrubland through burning. This conversion was carried out by small, largely subsistence-based populations in places far from permanent settlements, and it occurred in only a few decades. To understand the sequence of events that led to the island’s rapid deforestation, we used high-resolution charcoal and pollen records to reconstruct the watershed history of 16 small lakes in South Island, New Zealand. We also analyzed changes in species composition of diatoms and chironomid communities and variation in element concentrations to identify disturbance-related limnobiotic and biogeochemical changes within burned watersheds. Several high-severity fire events occurred within two centuries of first known M?ori presence, and changes in vegetation, erosion, and lake chemistry accompanied the events. Proxies of past climate suggest that human activity alone was responsible for this increased fire activity rather than unusually dry or warm conditions. In the 19th century, Europeans triggered further watershed change and transformed scrub to pastoral grasslands. The New Zealand example runs counter to studies which highlight the transition from hunter-gatherer to agro-pastoralism as the primary driver of land cover change. Human arrival in New Zealand highlights the degree to which even small populations of people can alter important ecosystem processes through land-use change alone.