The aim of this study was to describe the epidemiology of problem drinking in a cohort of women at high-risk of HIV in Kampala, Uganda. Overall, 1027 women at high risk of HIV infection were followed from 2008 to 2013. The CAGE and AUDIT questionnaires were used to identify problem drinkers in the cohort. Interviewer-administered questionnaires were used to ascertain socio-demographic and behavioural factors. Blood and genital samples were tested for HIV and other sexually transmitted infections. At enrollment, most women (71%) reported using alcohol at least weekly and about a third reported having drunk alcohol daily for at least 2 weeks during the past 3 months. Over half (56%) were problem drinkers by CAGE at enrollment, and this was independently associated with vulnerability (being divorced/separated/widowed, less education, recruiting clients at bars/clubs, and forced sex at first sexual experience). Factors associated with problem drinking during follow-up included younger age, meeting clients in bars/clubs, number of clients, using drugs and HSV-2 infection. HIV prevalence was associated with drinking at enrollment, but not during follow-up. This longitudinal study found high levels of persistent problem drinking. Further research is needed to adapt and implement alcohol-focused interventions in vulnerable key populations in sub-Saharan Africa.