Intersections between migration and sex work are underexplored in southern Africa, a region with high internal and cross-border population mobility, and HIV prevalence. Sex work often constitutes an important livelihood activity for migrant women. In 2010, sex workers trained as interviewers conducted cross-sectional surveys with 1,653 female sex workers in Johannesburg (Hillbrow and Sandton), Rustenburg and Cape Town. Most (85.3 %) sex workers were migrants (1396/1636): 39.0 % (638/1636) internal and 46.3 % (758/1636) cross-border. Cross-border migrants had higher education levels, predominately worked part-time, mainly at indoor venues, and earned more per client than other groups. They, however, had 41 % lower health service contact (adjusted odds ratio = 0.59; 95 % confidence interval = 0.40–0.86) and less frequent condom use than non-migrants. Police interaction was similar. Cross-border migrants appear more tenacious in certain aspects of sex work, but require increased health service contact. Migrant-sensitive, sex work-specific health care and health education are needed.