INTRODUCTION:There are significant knowledge gaps concerning complex forms of mobility emergent in sub-Saharan Africa, their relationship to sexual behaviours, HIV transmission, and how sex modifies these associations. This study, within an ongoing test-and-treat trial (SEARCH, NCT01864603), sought to measure effects of diverse metrics of mobility on behaviours, with attention to gender. METHODS:Cross-sectional data were collected in 2016 from 1919 adults in 12 communities in Kenya and Uganda, to examine mobility (labour/non-labour-related travel), migration (changes of residence over geopolitical boundaries) and their associations with sexual behaviours (concurrent/higher risk partnerships), by region and sex. Multilevel mixed-effects logistic regression models, stratified by sex and adjusted for clustering by community, were fitted to examine associations of mobility with higher-risk behaviours, in past 2 years/past 6 months, controlling for key covariates. RESULTS:The population was 45.8% male and 52.4% female, with mean age 38.7 (median 37, IQR: 17); 11.2% had migrated in the past 2 years. Migration varied by region (14.4% in Kenya, 11.5% in southwestern and 1.7% in eastern and Uganda) and sex (13.6% of men and 9.2% of women). Ten per cent reported labour-related travel and 45.9% non-labour-related travel in past 6 months-and varied by region and sex: labour-related mobility was more common in men (18.5%) than women (2.9%); non-labour-related mobility was more common in women (57.1%) than men (32.6%). In 2015 to 2016, 24.6% of men and 6.6% of women had concurrent sexual partnerships; in past 6 months, 21.6% of men and 5.4% of women had concurrent partnerships. Concurrency in 2015 to 2016 was more strongly associated with migration in women [aRR = 2.0, 95% CI(1.1 to 3.7)] than men [aRR = 1.5, 95% CI(1.0 to 2.2)]. Concurrency in past 6 months was more strongly associated with labour-related mobility in women [aRR = 2.9, 95% CI(1.0 to 8.0)] than men [aRR = 1.8, 95% CI(1.2 to 2.5)], but with non-labour-related mobility in men [aRR = 2.2, 95% CI(1.5 to 3.4)]. CONCLUSIONS:In rural eastern Africa, both longer-distance/permanent, and localized/shorter-term forms of mobility are associated with higher-risk behaviours, and are highly gendered: the HIV risks associated with mobility are more pronounced for women. Gender-specific interventions among mobile populations are needed to combat HIV in the region.