Humans have transformed Europe's landscapes since the establishment of the first agricultural societies in the mid-Holocene. The most important anthropogenic alteration of the natural environment was the clearing of forests to establish cropland and pasture, and the exploitation of forests for fuel wood and construction materials. While the archaeological and paleoecological record documents the time history of anthropogenic deforestation at numerous individual sites, to study the effect that prehistoric and preindustrial deforestation had on continental-scale carbon and water cycles we require spatially explicit maps of changing forest cover through time. Previous attempts to map preindustrial anthropogenic land use and land cover change addressed only the recent past, or relied on simplistic extrapolations of present day land use patterns to past conditions. In this study we created a very high resolution, annually resolved time series of anthropogenic deforestation in Europe over the past three millennia by 1) digitizing and synthesizing a database of population history for Europe and surrounding areas, 2) developing a model to simulate anthropogenic deforestation based on population density that handles technological progress, and 3) applying the database and model to a gridded dataset of land suitability for agriculture and pasture to simulate spatial and temporal trends in anthropogenic deforestation. Our model results provide reasonable estimations of deforestation in Europe when compared to historical accounts. We simulate extensive European deforestation at 1000 BC, implying that past attempts to quantify anthropogenic perturbation of the Holocene carbon cycle may have greatly underestimated early human impact on the climate system.