Research on men who have sex with men (MSM) in Africa is severely constrained. This paper examines the process of engaging MSM in research in a context where same-sex relationships are criminalised and socially stigmatised. Despite difficulties in researching MSM in Kenya, a convenient sample of 500 men was enrolled into a study aimed at understanding HIV/STI risks and prevention needs. Lessons drawn from this study highlight innovative methodological approaches and processes to working with and researching MSM in homophobic communities. Researchers willing to venture into MSM research in such contexts should be prepared to deal with among others, issues such as, seeking ethical approval for a study whose subjects are considered to engage in illegal activities, assuring study participants of their privacy and confidentiality and questioning of their own integrity. This study shows that despite difficulties, research of this kind can be carried out in Kenya.