A consultation was hosted in South Africa (March 2011) to assess the combination HIV prevention research priorities of academics, implementers and MSM community leaders. Sixty-nine participants, representing 17 African countries, participated. Interactive strategies were used to present current data on HIV interventions and discussions on research possibilities were facilitated with research priorities identified using the nominal group technique. Data were analysed using directed content analysis. Health worker training, social mobilisation, and community engagement were prioritised as structural interventions. Comprehensive counselling was identified as the most important behavioural intervention, with adherence, mental health, and risk reduction counselling identified as key counselling topics. Rectal microbicides, oral pre-exposure prophylaxis and condom and lubricant distribution were the most important biomedical interventions. This consultation resulted in the first combination HIV prevention research agenda for MSM in Africa. Outcomes will inform future research and be used to advocate for combination approaches to HIV prevention for MSM.