Land degradation – defined by the Economics of Land Degradation (ELD) initiative as a “reduction in the economic value of ecosystem services and goods derived from land” – is a serious impediment to improving rural livelihoods and food security of millions of people in the Eastern Africa region. The objectives of this paper are three fold; to identify the state, extent and patterns of land degradation, to estimate the costs of land degradation, and to compares the costs of action against inaction against land degradation using the Total Economic Value approach in four countries – Ethiopia, Kenya, Malawi and Tanzania. Results show that land degradation hotspots cover about 51%, 41%, 23% and 22% of the terrestrial areas in Tanzania, Malawi, Ethiopia and Kenya respectively. Following the Total Economic Value (TEV) framework, the cost of land degradation between 2001-2009 periods is about 2 billion USD in Malawi, 11 billion USD in Kenya, 18 billion USD in Tanzania and 35 billion USD in Ethiopia. These represents about 5%, 7%, 14% and 23%, of GDP in Kenya, Malawi, Tanzania and Ethiopia respectively. Taking action against land degradation is more favorable than inaction in both short-term (6 year) and a long-term (30 year) periods. During the 30-year period, for every dollar spent on taking action against land degradation users will expect a return of about $ 4.2 in Ethiopia, $ 4.1 in Kenya, $ 3.8 in Tanzania, and $ 3.7 in Malawi.