The island of Madagascar has a unique biodiversity, mainly located in the tropical forests of the island. This biodiversity is highly threatened by anthropogenic deforestation. Existing historical forest maps at national level are scattered and have substantial gaps which prevent an exhaustive assessment of long-term deforestation trends in Madagascar. In this study, we combined historical national forest cover maps (covering the period 1953–2000) with a recent global annual tree cover loss dataset (2001–2014) to look at six decades of deforestation and forest fragmentation in Madagascar (from 1953 to 2014). We produced new forest cover maps at 30¿m resolution for the year 1990 and annually from 2000 to 2014 over the full territory of Madagascar. We estimated that Madagascar has lost 44% of its natural forest cover over the period 1953–2014 (including 37% over the period 1973–2014). Natural forests cover 8.9¿Mha in 2014 (15% of the national territory) and include 4.4¿Mha (50%) of moist forests, 2.6¿Mha (29%) of dry forests, 1.7¿Mha of spiny forests (19%) and 177 000 ha (2%) of mangroves. Since 2005, the annual deforestation rate has progressively increased in Madagascar to reach 99 000¿ha/yr during 2010–2014 (corresponding to a rate of 1.1%/yr). Around half of the forest (46%) is now located at less than 100¿m from the forest edge. Our approach could be replicated to other developing countries with tropical forest. Accurate forest cover change maps can be used to assess the effectiveness of past and current conservation programs and implement new strategies for the future. In particular, forest maps and estimates can be used in the REDD+ framework which aims at “Reducing Emissions from Deforestation and forest Degradation” and for optimizing the current protected area network.