Global food demand is growing rapidly. Livestock grazing can provide a valuable source of protein, but conventional grazing is often unsustainable. We studied an 800,000-ha section of a threatened ecoregion in southeastern Australia. Conventional management in the region involves continuous livestock grazing with few rest periods and regular fertilizer application. By using remotely sensed data on tree cover and extensive field data on livestock grazing regimes, soil chemistry, tree diameters, and tree regeneration, we show that the region is facing a tree regeneration crisis. Under conventional management, across the region, millions of hectares of land currently supporting tens of millions of trees will be treeless within decades from now. This would have severe negative ramifications for biodiversity and key ecosystem services, including water infiltration and shade provision for livestock. However, we identified an unexpected win-win solution for tree regeneration and commercial grazing. A relatively new practice in the region is fast-rotational grazing, characterized by prolonged rest periods in between short, intensive grazing events. The probability of regeneration under fast-rotational grazing was up to 4-fold higher than under conventional grazing, and it did not differ significantly from the probability of regeneration in ungrazed areas. In addition, trees were more likely to regenerate where soil nutrient levels were low. These findings suggest that the tree regeneration crisis can be reversed by applying low-input, fast-rotational grazing. New policy settings supporting these practices could signal a turning point for the region, from ecological decline to ecological recovery.