We aimed to estimate the risk of COVID-19 outbreaks associated with air travel to a COVID-19-free country [New Zealand (NZ)]. A stochastic version of the SEIR model CovidSIM v1.1, designed specifically for COVID-19 was utilised. We first considered historical data for Australia before it eliminated COVID-19 (equivalent to an outbreak generating 74 new cases/day) and one flight per day to NZ with no interventions in place. This gave a median time to an outbreak of 0.2 years (95% range of simulation results: 3 days to 1.1 years) or a mean of 110 flights per outbreak. However, the combined use of a pre-flight PCR test of saliva, three subsequent PCR tests (on days 1, 3 and 12 in NZ), and various other interventions (mask use and contact tracing) reduced this risk to one outbreak after a median of 1.5 years (20 days to 8.1 years). A pre-flight test plus 14 days quarantine was an even more effective strategy (4.9 years; 2,594 flights). For a much lower prevalence (representing only two new community cases per week in the whole of Australia), the annual risk of an outbreak with no interventions was 1.2% and had a median time to an outbreak of 56 years. In contrast the risks associated with travellers from Japan and the United States was very much higher and would need quarantine or other restrictions. Collectively, these results suggest that multi-layered interventions can markedly reduce the risk of importing the pandemic virus via air travel into a COVID-19-free nation. For some low-risk source countries, there is the potential to replace 14-day quarantine with alternative interventions. However, all approaches require public and policy deliberation about acceptable risks, and continuous careful management and evaluation.