Mobility in sub-Saharan Africa links geographically-separate HIV epidemics, intensifies transmission by enabling higher-risk sexual behavior, and disrupts care. This population-based observational cohort study measured complex dimensions of mobility in rural Uganda and Kenya. Survey data were collected every 6 months beginning in 2016 from a random sample of 2308 adults in 12 communities across three regions, stratified by intervention arm, baseline residential stability and HIV status. Analyses were survey-weighted and stratified by sex, region, and HIV status. In this study, there were large differences in the forms and magnitude of mobility across regions, between men and women, and by HIV status. We found that adult migration varied widely by region, higher proportions of men than women migrated within the past one and five years, and men predominated across all but the most localized scales of migration: a higher proportion of women than men migrated within county of origin. Labor-related mobility was more common among men than women, while women were more likely to travel for non-labor reasons. Labor-related mobility was associated with HIV positive status for both men and women, adjusting for age and region, but the association was especially pronounced in women. The forms, drivers, and correlates of mobility in eastern Africa are complex and highly gendered. An in-depth understanding of mobility may help improve implementation and address gaps in the HIV prevention and care continua.