Previous surveys of men who have sex with men (MSM) in Africa have not adequately profiled HIV status and risk factors by sex work status. MSM in Nairobi, Kenya, were recruited using respondent-driven sampling, completed a behavioral interview, and were tested for HIV and sexually transmitted infections. Overlapping recruitment among 273 male sex workers and 290 other MSM was common. Sex workers were more likely to report receptive anal sex with multiple partners (65.7% versus 18.0%, P < 0.001) and unprotected receptive anal intercourse (40.0% versus 22.8%, P = 0.005). Male sex workers were also more likely to be HIV infected (26.3% versus 12.2%, P = 0.007).