Objectives: To describe the demographic and behavioural factors associated with HIV testing among migrant Africans in London. Methods: A cross sectional survey of migrants from five sub-Saharan African communities (Congo, Kenya, Uganda, Zambia, Zimbabwe) resident in London was carried out. The study formed part of a larger community based participatory research initiative with migrant African communities in London—the MAYISHA project. Trained, ethnically matched interviewers recruited study participants in a variety of community venues. A brief self completion questionnaire collected data on demographic characteristics, utilisation of sexual health services, HIV testing history, sexual behaviour, and attitudes. Results: Valid questionnaires were obtained from 748 participants (396 men and 352 women), median ages 31 and 27 years, respectively. Median length of UK residence was 6 years. 34% of men and 30% of women reported ever having had an HIV test. HIV testing was significantly associated with age and previous STI diagnosis among women; and additionally, nationality, education, employment, and self perceived risk of acquiring HIV among men. After controlling for significant demographic variables, previous diagnosis of an STI (adjusted odds ratio and 95% confidence interval for men: 2.96, 1.63 to 5.38, and women 2.03, 1.06 to 3.88) and perceived risk of acquiring HIV for men (adjusted OR 2.28, 95%CI 1.34 to 3.90) remained independently associated. Conclusion: Among these high HIV prevalence migrant communities, these data suggest that HIV testing remains largely associated with an individual’s STI history or self perceived risk. This strategy may be inappropriate given the potential for onward and vertical transmission. Antenatal HIV testing combined with proactive targeted HIV testing promotion should be prioritised.