Savannas cover the greater part of Africa and Australia and almost half of South America and contribute to the livelihoods of more than 350 million people. With the intensification of land use during the second half of the 20th century, savannas have become increasingly degraded through bush encroachment as a consequence of increased grazing pressure. Research on rangeland dynamics, however, provides contradicting answers with regard to the causes and possible remedies of bush encroachment. In this paper we present results from an application of a simulation-optimization model to the case of extensive rangeland management in South Africa. Our model differs from previous approaches in that it explicitly accounts for the influence of stochastic prices and rainfall on economically optimal management decisions. By showing the implications of neglecting price variation and stochasticity in rangeland models we provide new insights with regard to the determinants of bush encroachment and rangeland managers' economic utility. We demonstrate that, in the case of South Africa, optimal rangeland management is likely to lead to bush encroachment that eventually makes livestock holding unprofitable. Yet, we identify the costs of fire management to be a limiting factor for managers to counteract bush encroachment and explore the impact of policy measures to reduce fire control costs on the ecological and economic sustainability of livestock holding.