Background: The contribution of women's mobility to the HIV/AIDS epidemic in Africa is poorly understood, despite women's high mobility and evidence that it is associated with higher-risk sexual behavior. We sought to measure levels of mobility, HIV prevalence, and related risk behaviors among female traders in Kisumu, Kenya. Methods: We used global positioning system mapping to develop a probability-based sample and recruited 305 female market traders for participation in a survey and voluntary HIV counseling and testing in 2014. We estimated HIV prevalence and fitted logistic regression models to measure associations between mobility, risk behaviors, and HIV infection. Results: HIV prevalence was 25.6% (95% confidence interval: 21.0 to 30.8); 11.5% had migrated (changed residence, over county, or national boundary) in the past year and 39.3% in the past 5 years. More than one-third (38.3%) spent nights away from main residence in the past month, with 11.4% spending more than a week away. Multiple partners were reported by 13.1% of women in the last year; 16% of married women reported a concurrent partnership. Mobility was not significantly associated with HIV prevalence, although recent short-term mobility was significantly correlated with higher numbers of sexual partners in the past year. Conclusions: Female market traders were highly mobile, and HIV prevalence among traders was higher than in the general population of women of reproductive age in Kisumu (15.3% in 2013), and Nyanza Province, Kenya (16.1% in 2012). High HIV prevalence and risk behavior among women in this study warrant accelerated attention to HIV prevention and care needs of mobile women, including market traders.