Rwanda has responded strongly to HIV/AIDS, but prevention among men who have sex with men (MSM) has not yet been addressed due to a strong cultural resistance to homosexuality, and a lack of data showing the public health value of attending to the sexual health needs of this group. We conducted an exploratory study on HIV risk among MSM in Kigali using snowball sampling involving peer leaders. The 99 respondents were demographically, socially, and sexually diverse. Respondents reported relatively high numbers of male and female partners, and considerable HIV risk behaviors including commercial sex with men and women, low condom use during anal and vaginal sex, and high mobility. Many respondents reported verbal and/or physical abuse due to their sexuality. This first study of MSM in Rwanda has brought attention to a previously neglected HIV risk group and their potential driving role in the Rwandan epidemic, demonstrating the need for sensitive and targeted interventions.