Cost-effective surveillance strategies are needed for efficient responses to biological invasions and must account for the trade-offs between surveillance effort and management costs. Less surveillance may allow greater population growth and spread prior to detection, thereby increasing the costs of damages and control. In addition, surveillance strategies are usually applied in environments under continual invasion pressure where the number, size and location of established populations are unknown prior to detection. We develop a novel modeling framework that accounts for these features of the decision and invasion environment and determines the long term sampling effort that minimises the total expected costs of new invasions. The optimal solution depends on population establishment and growth rates, sample sensitivity, and sample, eradication, and damage costs. We demonstrate how to optimise surveillance systems under budgetary constraints and find that accounting for spatial heterogeneity in sampling costs and establishment rates can greatly reduce management costs.