Substantial revegetation is required across much of Australian agricultural landscapes. Managers need to minimise the risks of failure and costs associated with revegetation. Whereas ‘natural regeneration’ of eucalypts is relatively cheap compared with direct seeding or planting tubes, natural regeneration in grazed lands occurs infrequently and under limited circumstances. Management needs to understand the situations in which natural regeneration is most likely to occur and what actions can improve the chances of regeneration. We used a rule- and stage-based model of eucalypt regeneration focusing on events between seed supply and sapling escape to synthesise current knowledge and learn how to improve the success rate of natural regeneration of eucalypts. The model used deterministic rules but with stochastic rainfall, and fire was applied stochastically as well as deterministically. Results from simulations suggested that low-productivity pastures have greater likelihood of supporting saplings than do high-productivity pastures. Fire and grazing can increase the chances of subsequent germination and early seedling survival, particularly in high-productivity pastures. As a result, management actions, such as fire and strategic grazing, can improve the probability of sapling establishment in a high-productivity pasture; however, frequency and timing of management actions are important. The following three sources of uncertainty appear crucial: first, variability in rainfall; second, uncertainty about rainfall effects on stage transitions; and third, variability in seed supply. These uncertainties can overwhelm improvements to the chances of regeneration owing to management interventions. Because rainfall and seed supply have overwhelming effects on the process of regeneration, they limit the ability of managers to influence the outcomes and this makes investment in natural regeneration inherently risky. Thus, better data are needed on the effect of rainfall on stage transitions and on spatial and temporal variation in seed supply. This would aid managers to estimate the likelihood of success of regeneration, and make decisions about if, when and where to invest in natural regeneration and what actions to implement.