The effects of stock grazing on native grassy ecosystems in temperate southern Australia are well documented. However, less is known about the potential of ecosystems to recover after a long history of stock grazing and, in particular, whether the removal of stock will have positive, negative or neutral impacts on biodiversity. We examined the response of understorey vegetation to the removal of sheep grazing in a herb‐rich Eucalyptus camaldulensis (red gum) woodland in western Victoria. Using a space‐for‐time chronosequence, woodlands were stratified into groups based on their time‐since‐grazing removal; these were long‐ungrazed (>20 years), intermediate‐time‐since‐grazing (9–14 years), recently ungrazed (5 years) and continuously grazed. We found significantly higher species density in long‐ungrazed sites relative to sites with a more recent grazing history. No differences were found in species density between continuously grazed sites and those ungrazed in the previous 14 years. Species composition differed with time‐since‐grazing removal and indicator species analysis detected several native species (including tall native geophytes and herbs) associated with long‐ungrazed sites that were absent or in low abundance in the more recently grazed sites. Seven of the eight species significantly associated with continuously grazed sites were exotic. Removal of sheep grazing in red gum woodlands can have positive benefits for understorey diversity but it is likely that recovery of key indicators such as native species will be slow.