Woodlands, which are part of the landscape and an important source of livelihood for smallholders living in the environmentally vulnerable Central Rift Valley (CRV) of Ethiopia, are experiencing rapid changes. Detecting and monitoring these changes is essential for better management of the resources and the benefits they provide to people. The study used a combination of both quantitative and qualitative methods to analyze the extent and pattern of woodland cover changes from 1973 to 2013. Pixel-based supervised image classification with a maximum likelihood classification algorithm was used for land cover classification and change detection analyses. Local peoples’ perceptions were used to explain the patterns of change and their possible reasons. Four major land cover classes were identified, with an overall accuracy of 88.3% and a Kappa statistic of 0.81 for the latest image. The analysis revealed a major land cover reversal, where woodland (92.4%) was the dominant land cover in 1973, while it was agriculture (44.7%) in 2013. A rapid reduction in woodland (54%) and forest (99%) covers took place between 1973 and 2013, with the majority of the conversions being made during the government transition period (1973 to 1986). Agriculture (3878%) and grassland (11,117%) increased tremendously during the 40-year period at the expense of woodlands and forests. Bare land increased moderately (40%). Thus, woodlands are under increasing pressure from other land uses, particularly agriculture, and declining faster. If the current trends of land cover change remain unabated it is likely that woodlands will disappear from the landscape of the area in the near future. Therefore, better forest policy and implementation tools, as well as better woodland management strategies and practices, need to be in place for woodlands to continue providing vital ecosystem goods and services to the local people, as well as to the environment.