Background: To prevent the spread of COVID-19 in Newfoundland & Labrador (NL), NL implemented a wide travel ban in May 2020. We estimate the effectiveness of this travel ban using a customized agent-based simulation (ABS). Methods: We built an individual-level ABS to simulate the movements and behaviors of every member of the NL population, including arriving and departing travellers. The model considers individual properties (spatial location, age, comorbidities) and movements between environments, as well as age-based disease transmission with pre-symptomatic, symptomatic, and asymptomatic transmission rates. We examine low, medium, and high travel volume, traveller infection rates, and traveller quarantine compliance rates to determine the effect of travellers on COVID spread, and the ability of contact tracing to contain outbreaks. Results: Infected travellers increased COVID cases by 2-52x (8-96x) times and peak hospitalizations by 2-49x (8-94x), with (without) contact tracing. Although contact tracing was highly effective at reducing spread, it was insufficient to stop outbreaks caused by travellers in even the best-case scenario, and the likelihood of exceeding contact tracing capacity was a concern in most scenarios. Quarantine compliance had only a small impact on COVID spread; travel volume and infection rate drove spread. Interpretation: NL’s travel ban was likely a critically important intervention to prevent COVID spread. Even a small number of infected travellers can play a significant role in introducing new chains of transmission, resulting in exponential community spread and significant increases in hospitalizations, while outpacing contact tracing capabilities. With the presence of more transmissible variants, e.g., the UK variant, prevention of imported cases is even more critical.