The arrival in Australia of Europeans and the species they brought with them initiated a sharp decline in native mammalian biodiversity. Consequently, one-third of the original or pre-European terrestrial mammal fauna is now extinct or threatened with extinction. Although the distributional ranges of many Australian mammals have contracted markedly, modern distributions are frequently used as baselines for conservation management and understanding ecological requirements. However, these often poorly reflect pre-European distributions, particularly in areas where biodiversity declines were rapid and occurred soon after European arrival. Here we analyse two late Holocene mammalian assemblages from Fleurieu Peninsula, South Australia, and reconstruct the pre-European terrestrial non-volant mammal fauna. The region was previously estimated to have lost perhaps 30% of its original terrestrial non-volant mammal fauna, but our results indicate a loss of almost 50%. We provide the first local records of the murids Mastacomys fuscus, Pseudomys australis, P. gouldii, P. novaehollandiae and P. shortridgei, and confirm the past occurrence of the now-extinct Conilurus albipes. Our study contributes new knowledge of species biogeography and ecology and will help refine restoration targets.