1. Invasive vertebrate species are a world-wide threat to biodiversity and agricultural production. The presence of foxes, one of the most damaging invasive vertebrates introduced to Australia, has now been confirmed in the island state of Tasmania, placing at risk many species of native vertebrates and substantial agricultural industry. 2. Effective eradication of such a rare but elusive carnivore requires robust strategies informed by novel but systematic detection. 3. We combine DNA detection approaches for trace samples with systematic stratified and opportunistic surveys of carnivore scats to estimate the current distribution of foxes in Tasmania. We use that DNA evidence and other hard evidence provided by carcasses and other material to build a predictive model of fox habitat suitability for all of Tasmania. 4. We demonstrate that this destructive species is widespread in northern and eastern Tasmania but has not yet reached the limits of its range. The widespread nature of this distribution reveals that targeting fox activity hotspots only for eradication is unlikely to be successful and that a strategic and state wide approach is required. Our habitat suitability model can provide a basis for prioritizing areas for fox management. 5. Synthesis and applications. Our approach highlights the importance of early and preemptive surveys of recently established, and therefore rare, invasive species and the necessity of providing a sound and defensible approach to determining the distribution of the invasive species. This approach provides a template for the systematic detection of rare cryptic carnivores.