This study compared HIV-related sexual behavior among mobile and non-mobile populations in Burkina Faso and identified venues where HIV/AIDS interventions targeting mobile individuals should be implemented. Men (N = 940) and women (N = 430) responded to a sexual behavior survey while socializing at venues where people meet sexual partners in eight Burkina Faso villages. Mobile women were more likely than non-mobile women to report new sexual partnerships (adjusted prevalence odds ratio (POR): 2.07, 95% confidence interval (CI): 1.19-3.59) and transactional sex (adjusted POR: 2.30, 95% CI: 1.55-3.42) in the past month. Mobility was most common and associations between mobility and sexual partnership levels were particularly strong among women interviewed in urban commercial towns situated near international borders. Mobile women were most likely to be interviewed at venues such as bars and clubs, making these appropriate locations for HIV/AIDS interventions. Mobility was not associated with HIV-related sexual behaviors among men.