As reported by FAO (2005 State of the World’s Forests (Rome: UNFAO), 2010 Forest Resource Assessment (FRA) 2010/095 (Rome: UNFAO)), Indonesia experiences the second highest rate of deforestation among tropical countries. Hence, timely and accurate forest data are required to combat deforestation and forest degradation in support of climate change mitigation and biodiversity conservation policy initiatives. Within Indonesia, Sumatra Island stands out due to the intensive forest clearing that has resulted in the conversion of 70% of the island’s forested area through 2010. We present here a hybrid approach for quantifying the extent and change of primary forest in Sumatra in terms of primary intact and primary degraded classes using a per-pixel supervised classification mapping followed by a Geographic Information System (GIS)-based fragmentation analysis. Loss of Sumatra’s primary intact and primary degraded forests was estimated to provide suitable information for the objectives of the United Nations Framework on Climate Change (UNFCCC) Reducing Emission from Deforestation and Forest Degradation (REDD and REDD+) program. Results quantified 7.54 Mha of primary forest loss in Sumatra during the last two decades (1990–2010). An additional 2.31 Mha of primary forest was degraded. Of the 7.54 Mha cleared, 7.25 Mha was in a degraded state when cleared, and 0.28 Mha was in a primary state. The rate of primary forest cover change for both forest cover loss and forest degradation slowed over the study period, from 7.34 Mha from 1990 to 2000, to 2.51 Mha from 2000 to 2010. The Geoscience Laser Altimeter System (GLAS) data set was employed to evaluate results. GLAS-derived tree canopy height indicated a significant structural difference between primary intact and primary degraded forests (mean height 28 m ± 8.7 m and 19 m ± 8.2 m, respectively). The results demonstrate a method for quantifying primary forest cover stand-replacement disturbance and degradation that can be replicated across the tropics in support of REDD+ initiatives.