Palatable shrubs and trees in rangelands are vulnerable to grazing impacts, with local extinctions and declines documented. However, population trends are difficult to detect due to longevity of individuals and poor understanding of regeneration. We investigated the demography and conservation status of the Grey Range fuchsia (Eremophila stenophylla Chinnock), a geographically restricted and palatable shrub endemic to south-west Queensland. We documented 28 populations over 30,400 km2, with an estimated total population size of 17,000 individuals. Seedling recruitment is rare and seedlings were observed at six populations, all with low or intermittent grazing pressure. In contrast, vegetative recruits were recorded at 19 populations and comprised at least 28% of plants measured. Resprouting confers some resilience to individuals, although repeated browsing restricts plant growth, limiting flowering and fruiting. Consistently heavily grazed populations also contain fewer plants. Although Eremophila stenophylla is secure in numerous populations with low grazing pressure, it qualifies as Vulnerable under IUCN Red List criteria due to past and ongoing decline at more than half of its populations. Grazing relief is necessary to ensure the long-term persistence of these populations. We predict that similar trajectories apply to other semi-arid shrubs, and research is required to inform grazing management to avert local extinctions.