Invasive species can lead to community-level damage to the invaded ecosystem and extinction of native species. Most surveillance systems for the detection of invasive species are developed based on expert assessment, inherently coming with a level of uncertainty. In this research, info-gap decision theory (IGDT) is applied to model and manage such uncertainty; surveillance of the Asian House Gecko, Hemidactylus frenatus Duméril and Bibron, 1836 on Barrow Island, is used as a case study. Our research provides a novel method for applying IGDT to determine the robust population threshold (K) to trigger detection, robust-optimizing surveillance costs rather than minimizing surveillance costs. We demonstrate that increasing the population threshold for detection increases both robustness to the errors in the model parameter estimates, and opportuneness to lower surveillance costs than the accepted maximum budget. This paper provides guidance for decision makers to balance robustness and required surveillance expenditure. IGDT offers a novel method to model and manage the uncertainty prevalent in biodiversity conservation practices and modelling. The method outlined here can be used to design robust surveillance systems for invasive species in a wider context, and to better tackle uncertainty in protection of biodiversity and native species in a cost-effective manner.