Massive environmental changes have occurred since European settlement of Australia more than 200 years ago. We examined the demographics of Callitris columellaris F. Muell. (Cupressaceae) across Australia as a potential bio-indicator of environmental change. This species is a widespread obligate seeder with large reproductive potential but is sensitive to fire and herbivory. We measured variation in tree size, stem density, basal area, and seedling recruitment among 90 sites that encompassed a wide range of climates and landscape settings across Australia. Soils from each site were analysed for pH, %C, % N and %P. We also noted evidence of fire and herbivory. Climate at each site was classified as tropical, temperate or arid. Case studies and published literature are used to illustrate the contrasting effects of disturbance in the three climate zones. Climate had a strong influence on stand basal area, density of juveniles and proportions of seedlings and saplings in a population, as well as on prevailing disturbance regimes. Structure of Callitris populations was not strongly associated with soil fertility. In the arid zone overall, and in many individual populations, there were relatively few juveniles and evidence of a chronic recruitment deficit during the last 100–200 years, consistent with reported adverse effects of introduced herbivores on Callitris regeneration. By contrast, most tropical and temperate populations conformed to a negative exponential distribution, consistent with frequent regeneration. Many temperate sites showed extremely dense juvenile populations. In the tropics, juvenile density is lower, probably because of frequent, relatively mild fires that kill many juveniles but few adult trees. We conclude that C. columellaris is a sensitive bio-indicator, and is in decline across much of arid Australia, reflecting the inherent vulnerability of ecosystems in regions with low productivity.