Brazil currently has one of the fastest growing SARS-CoV-2 epidemics in the world. Owing to limited available data, assessments of the impact of non-pharmaceutical interventions (NPIs) on virus spread remain challenging. Using a mobility-driven transmission model, we show that NPIs reduced the reproduction number from >3 to 1–1.6 in São Paulo and Rio de Janeiro. Sequencing of 427 new genomes and analysis of a geographically representative genomic dataset identified >100 international virus introductions in Brazil. We estimate that most (76%) of the Brazilian strains fell in three clades that were introduced from Europe between 22 February11 March 2020. During the early epidemic phase, we found that SARS-CoV-2 spread mostly locally and within-state borders. After this period, despite sharp decreases in air travel, we estimated multiple exportations from large urban centers that coincided with a 25% increase in average travelled distances in national flights. This study sheds new light on the epidemic transmission and evolutionary trajectories of SARS-CoV-2 lineages in Brazil, and provide evidence that current interventions remain insufficient to keep virus transmission under control in the country.