Reconstruction of a species demographic history can be used to investigate impacts of environmental change through time. Australia’s mesic biome experienced massive changes during the Holocene, including climate fluctuations, increased human populations, and European settlement. Using microsatellite data from 202 brush-tailed rock-wallabies (Petrogale penicillata) sampled across the species current geographic range, we investigated gene flow and inferred the demographic history of the species to explore the historical impacts of environmental change on this once wide-ranging marsupial mammal. We found high levels of genetic diversity in all colonies, despite very restricted contemporary gene flow and no sign of historical gene flow. Demographic analyses showed that individual populations have low effective population sizes (N_e < 200). We identified a major historical decline throughout the species range occurring 10,000–1000 years before present, spanning a period with increased El Niño Southern Oscillation activity, increased human population size and establishment of the dingo population. This major decline pre-dates the European settlement of Australia and so places the species most recent dramatic decline into context, suggesting that brushed-tailed rock-wallabies were inherently vulnerable to major changes to their environment.