Early detection of biological invasions is critical to reducing their impact, but because invading organisms are initially at low densities, detection and eradication can be challenging. Here, we demonstrate the utility of faecal DNA analysis for the detection of an elusive invasive species – the red fox, Vulpes vulpes, which was illegally introduced to the island of Tasmania in the late 1990s. Foxes are a devastating pest to both wildlife and agriculture on the Australian mainland, and would have a similarly serious impact in Tasmania if they became established. Attempts to eradicate foxes from Tasmania have been hampered by unreliable distribution data derived mostly from public sightings. In response, we developed a highly accurate and reliable DNA-based PCR-multiplex test that identifies foxes from field-collected faeces. We also developed a sexing test, but it was reliable only for faeces less than three weeks old. Faeces are a useful target for DNA-based diagnostics in foxes because they are deposited in prominent locations and are long-lasting. The species identification test formed a key component of a Tasmania-wide detection and eradication program. In all, 1160 geo-referenced carnivore scats were analysed; of these, 78% contained DNA of sufficient quality for species identification. A single scat from the north-east of the island was identified as belonging to fox, as was a nine-week-old roadkill carcass from the north coast, and a blood sample from near Hobart, triggering increased control and surveillance in these regions. The accuracy, reliability, and cost-effectiveness of non-invasive tests make them a critical adjunct to traditional tools for monitoring cryptic invasive species that are at low density in the early stages of invasion and when eradication is still an option.