Questions: Fire and livestock grazing are regarded as current threats to biodiversity and landscape integrity in northern Australia, yet it remains unclear what biodiversity losses and habitat changes occurred in the 19-20th centuries as livestock and novel fire regimes were introduced by Europeans. What baseline is appropriate for assessing current and future environmental change?. Location: Australia's Kimberley region is internationally recognized for its unique biodiversity and cultural heritage. The region is home to some of the world's most extensive and ancient rock art galleries, created by Aboriginal peoples since their arrival on the continent 65,000 years ago. The Kimberley is considered one of Australia's most intact landscapes and its assumed natural vegetation has been mapped in detail. Methods: Interpretations are based on a continuous sediment record obtained from a waterhole on the Mitchell River floodplain. Sediments were analysed for geochemical and palynological proxies of environmental change and dated using 210Pb and 14C techniques. Results: We show that the present-day vegetation in and around the waterhole is very different to its pre-European counterpart. Pre-European riparian vegetation was dominated by Antidesma ghaesembilla and Banksia dentata, both of which declined rapidly at the beginning of the 20th century. Soon after, savanna density around the site declined and grasses became more prevalent. These vegetation shifts were accompanied by geochemical and biological evidence for increased grazing, local burning, erosion and eutrophication. Conclusions: We suggest that the Kimberley region's vegetation, while maintaining a 'natural' appearance, has been altered dramatically during the last 100 years through grazing and fire regime changes. Landscape management should consider whether the current (impacted) vegetation is a desirable or realistic baseline target for biodiversity conservation.