High resolution and low uncertainty deforestation maps covering large spatial areas in tropical countries are needed to plan efficient forest conservation and management programs such as REDD+ (Reducing Emissions from Deforestation and Forest Degradation). Using an open-source free software (R, GRASS and QGis) and an original statistical approach combining multi-date land cover observations based on Landsat satellite images and the random forests classifier, we obtained up-to-date deforestation maps for the periods 2000-2005 and 2005-2010 with a minimum mapping unit of 0.36 ha for 7.7 M hectares, i.e. 40.3% of the tropical humid forest and 20.6% of the tropical dry forest in Madagascar. Uncertainty in deforestation on the maps was calculated by comparing the results of the classification to more than 30,000 visual interpretation points on a regular grid. We assessed accuracy on a per-pixel basis (confusion matrix) and by measuring the relative surface difference between wall-to-wall approach and point sampling. At the pixel level, user accuracy was 84.7% for stable land cover and 60.7% for land cover change. On average for the whole study area, we obtained a relative difference of 2% for stable land cover categories and 21.1% land cover change categories respectively between the wallto- wall and the point sampling approach. Depending on the study area, our conservative assessment of annual deforestation rates ranged from 0.93 to 2.33%·yr?1 for the humid forest and from 0.46 to 1.17%·yr?1 for the dry forest. Here we describe an approach to obtain deforestation maps with reliable uncertainty estimates that can be transposed to other regions in the tropical world.