Objective To evaluate HIV and syphilis prevalence among men who have sex with men (MSM) in Nigeria, and assess their HIV-related risk behaviours and exposure to HIV prevention interventions. Methods Cross-sectional study using respondent-driven sampling conducted in Lagos, Kano and Cross River states, Nigeria, between July and September 2007. Results A total of 879 MSM participated, 293 from each state. Eight participants (1.1%, CI 0.1% to 2.2%) in Cross River, 27 (9.3%, CI 5.7% to 15.4%) in Kano and 74 (17.4%, CI 12.3% to 23.2%) in Lagos tested positive for HIV. No syphilis was detected. The median age was 22 years. MSM reported an average of 4.2 male anal sex partners in the past 6 months. Between 24.4% (Lagos) and 36.0% (Kano) of MSM reported selling sex to other men. Up to 49.7% of MSM reported sex with a girlfriend and #6.5% purchased sex from female sex workers. Consistent condom use in commercial sex with other men over the past 6 months ranged from 28.0% (Cross River) to 34.3% (Kano), in contrast to between 23.9% (Kano) and 45.8% (Lagos) for non-commercial sex. Associations with HIV positivity included age in the three states, having been the receptive partner in anal sex in the past 6 months in Lagos and in Lagos and Kano feeling at risk of HIV. Conclusion Large differentials in HIV prevalence between states together with high mobility, inconsistent condom use and behavioural links with female sex partners, have the potential for further HIV transmission within MSM networks, and between MSM and the general population.