Background: Growing travel connectivity and economic development have dramatically increased the magnitude of human mobility in Africa. In public health, vulnerable population groups such as mobile individuals are at an elevated risk of sexually transmitted diseases, including HIV. Methods: The population-based Demographic Health Survey data of five Southern African countries with different HIV epidemic intensities (Angola, Malawi, South Africa, Zambia, and Zimbabwe) were used to investigate the association between HIV serostatus and population mobility adjusting for socio-demographic, sexual behavior and spatial covariates. Results: Mobility was associated with HIV seropositive status only in Zimbabwe (adjusted odds ratio [AOR] = 1.37 [95% confidence interval [CI]: 1.01–1.67]). These associations were not significant in Angola, Malawi, South Africa, and Zambia. Females had higher odds of mobility than males in Zimbabwe (AOR = 1.37, CI: 1.10–1.69). The odds of mobility decreased with age in all five countries. Conclusions: Our findings highlight the heterogeneity of the social and health determinants of mobile populations in several countries with different HIV epidemic intensities. Effective interventions using precise geographic focus combined with detailed attribute characterization of mobile populations can enhance their impact especially in areas with high density of mobile individuals and high HIV prevalence.