Rangelands in southern Ethiopia have been undergoing a rapid regime shift from herbaceous to woody plant dominance in the past decades, reducing indigenous plant biodiversity, altering ecosystem function, and threatening subsistence pastoralism. Despite significant rangeland management implications, quantification of spatial encroachment extent and transitional pathways that result in encroachment remain largely under-explored. This paper develops a phenology-based approach to map rangeland vegetation states in southern Ethiopia, and examines transition pathways among states using the state-and-transition model. The results indicate that nearly 80% of landscape was dominated by woody plants in 2013. While stable encroached states have been established in both high and low lands through different transition pathways between 2003 and 2013, we identified spatial locations where bush encroachment occurred rapidly. The multiplicity in the transition pathways indicates opportunities for positive transformation in the entire rangeland system in southern Ethiopia and other semi-arid regions of Africa.