Tropical forests have been recognized as having global conservation importance. However, they are being rapidly destroyed in many regions of the world. Regular monitoring of forests is necessary for an adaptive management approach and the successful implementation of ecosystem management. The present study analyses the temporal changes in forest ecosystem structure in tribal dominated Malkangiri district of Orissa, India, during 1973–2004 period based on digitized forest cover maps using geographic information system (GIS) and interpretation of satellite data. Three satellite images Landsat MSS (1973), Landsat TM (1990) and IRS P6 LISS III (2004) were used to determine changes. Six land cover types were delineated which includes dense forest, open forest, scrub land, agriculture, barren land and water body. Different forest types were also demarcated within forest class for better understanding the degradation pattern in each forest types. The results showed that there was a net decrease of 475.7 km2 forest cover (rate of deforestation = 2.34) from 1973 to 1990 and 402.3 km2 (rate of deforestation = 2.27) from 1990 to 2004. Forest cover has changed over time depending on a few factors such as large-scale deforestation, shifting cultivation, dam and road construction, unregulated management actions, and social pressure. A significant increase of 1222.8 km2 agriculture area (1973–2004) clearly indicated the conversion of forest cover to agricultural land. These alterations had resulted in significant environmental consequences, including decline in forest cover, soil erosion, and loss of biodiversity. There is an urgent need for rational management of the remaining forest for it to be able to survive beyond next decades. Particular attention must be paid to tropical forests, which are rapidly being deforested.