Measuring trends in the size of prehistoric populations is fundamental to our understanding of the demography of ancient people and their responses to environmental change. Archaeologists commonly use the temporal distribution of radiocarbon dates to reconstruct population trends, but this can give a false picture of population growth because of the loss of evidence from older sites. We demonstrate a method for quantifying this bias, and we use it to test for population growth through the Holocene of Australia. We used model simulations to show how turnover of site occupation across an archaeological landscape, interacting with erasure of evidence at abandoned sites, can create an increase in apparent site occupation towards the present when occupation density is actually constant. By estimating the probabilities of abandonment and erasure from archaeological data, we then used the model to show that this effect does not account for the observed increase in occupation through the Holocene in Australia. This is best explained by population growth, which was low for the first part of the Holocene but accelerated about 5000 years ago. Our results provide new evidence for the dynamism of non-agricultural populations through the Holocene.