We provide the first fossil pollen and charcoal analysis from the island of Gran Canaria (Canary Islands). The pollen record obtained from Laguna de Valleseco (870 m a.s.l.) spans the late Holocene ( c. 4500–1500 cal. yr BP) and thereby captures the impact of human colonization. During the earliest period, pollen composition resembled contemporary thermophilous communities, with palms ( Phoenix canariensis) and junipers ( Juniperus cf. turbinata) being the dominant trees, suggesting that these elements were more widespread in the past. Vegetation in Valleseco began to change at around 2300 cal. yr BP, 400 years before the earliest archaeological evidence of human presence in the island ( c. 1900 cal. yr BP). Our data show an increased frequency of fires at that time, coinciding with the decline of palms and the increase of grasses, indicating that humans were present and were transforming vegetation, thus showing that the demise of Gran Canaria’s forest began at an early point in the prehistoric occupation of the island. In the following centuries, there were no signs of forest recovery. Pollen from cultivated cereals became significant, implying the introduction of agriculture in the site, by 1800 cal. yr BP. The next shift in vegetation ( c. 1600 cal. yr BP) involved the decrease of grasses in favour of shrubs and trees like Morella faya, suggesting that agriculture was abandoned at the site.