The great success of the Brazilian deforestation programme “PRODES digital” has shown the importance of annual deforestation information for understanding and mitigating deforestation and its consequences in Brazil. However, there is a lack of similar information on deforestation for the 1990s and 1980s. Such maps are essential to understand deforestation frontier development and related carbon emissions. This study aims at extending the deforestation mapping record backwards into the 1990s and 1980s for one of the major deforestation frontiers in the Amazon. We use an image compositing approach to transform 2224 Landsat images in a spatially continuous and cloud free annual time series of Tasseled Cap Wetness metrics from 1984 to 2012. We then employ a random forest classifier to derive annual deforestation patterns. Our final deforestation map has an overall accuracy of 85% with half of the overall deforestation being detected before the year 2000. The results show for the first time detailed patterns of the expanding deforestation frontier before the 2000s. The high degree of automatization exhibits the great potential for mapping the whole Amazon biome using long-term and freely accessible remote sensing collections, such as the Landsat archive and forthcoming Sentinel-2 data.