Brazil detected community transmission of COVID-19 on March 13, 2020. In this study we identified which areas in the country were the most vulnerable for COVID-19, both in terms of the risk of arrival of cases, the risk of sustained transmission and their social vulnerability. Probabilistic models were used to calculate the probability of COVID-19 spread from São Paulo and Rio de Janeiro, the initial hotspots, using mobility data from the pre-epidemic period, while multivariate cluster analysis of socio-economic indices was done to identify areas with similar social vulnerability. The results consist of a series of maps of effective distance, outbreak probability, hospital capacity and social vulnerability. They show areas in the North and Northeast with high risk of COVID-19 outbreak that are also highly socially vulnerable. Later, these areas would be found the most severely affected. The maps produced were sent to health authorities to aid in their efforts to prioritize actions such as resource allocation to mitigate the effects of the pandemic. In the discussion, we address how predictions compared to the observed dynamics of the disease.