The East African drylands cover about 47% of the land surface and host about 20 million people. Rural people living in the drylands are mainly pastoralists who depend on livestock for both economic and social well-being. During the dry season, pastoralists apply strategic mobility to access grazing resources efficiently. However, this strategy has experienced change and constraints due to various demographic- and climate-related challenges. Pastoral lands have been cleared for large-scale agriculture while pastoralists have shifted towards agro-pastoralism. This has eroded many dryland trees and forests leading to environmental degradation. This review discusses important indigenous trees that can be utilized in ecological restoration of drylands as well as providing ecosystem goods and services. These include trees for gums and resins (Acacia, CommiphoraandBoswellia), indigenous fruit trees (IFTs) (Adansonia digitata, Tamarindus indica and Balanites aegyptiaca), trees for wood (Melia volkensiiand Terminalia brownie) and fodder (Acacia tortilis andFaidherbia albida). They are not only drought-tolerant but also have minimal disruption to the ecosystem. Various dryland restoration strategies and constraints are also discussed. For successful establishment, seedling planting should be integrated with other appropriate practices such as natural regeneration, silviculture and enrichment planting for sustainable dryland management.