Background: Migrants from high endemic countries accounted for 18% of newly diagnosed HIV infections in Europe in 2017. Knowledge on the link between HIV risk and post-migration travels and their impact on HIV acquisition is scarce, but critical to inform prevention. This study aims to explore risky sexual behaviour and HIV-acquisition among sub-Saharan African migrants, and to assess post-migration mobility as a determinant of sexual risk behaviour. Methods: Data from two cross-sectional bio-behavioural surveys to assess HIV-prevalence conducted in Lisbon and Antwerp were analysed to explore migration-related characteristics, travel patterns, and sexual risk taking in the host country and abroad. Bi- and multivariate associations were estimated through adjusted odds ratios and 95% confidence intervals; multivariable logistic regression determined factors associated with condomless sexual intercourse. Results: Among N = 1508 participants above 18 years (58% males), 68% travelled post-migration (49.2% reported intercourse abroad). The overall proportion of condomless sex at last sexual intercourse was high (68.1%). The odds of condomless sex in the host country was five times higher when the last sexual intercourse abroad was also condomless [OR:5.32; 95% CI:2.98-9.25]. About half of the travellers reported concurrency, i.e. a regular partner in the host country while having other sexual partners abroad. Almost three percent of the participants reported being HIV+, but 5% had a reactive HIV test-result, with similar proportions among travellers and non-travellers. Also, among the n = 75 participants with reactive HIV test-results, condomless sex occurred (n = 40) and was associated with mobility. Conclusions: Sub-Saharan African migrants are mobile and engage in sexual risk behaviours in the countries of residence and while travelling, increasing risk of post-migration HIV-acquisition. A transnational perspective on HIV prevention and sexual health promotion is needed for effectively reducing migrants' HIV risk related to their mobility.