Objectives: To identify social and behavioral characteristics associated with sexual risk behaviors among male sex workers who sell sex to men in Mombasa, Kenya. Methods: Using time-location sampling, 425 men who had recently sold, and were currently willing to sell sex to men were invited to participate in a cross-sectional survey. A structured questionnaire was administered using handheld computers. Factors associated with self- reported unprotected anal sex with male clients in the past 30 days were identified and subjected to multivariate analysis. Results: Thirty-five percent of respondents did not know HIV can be transmitted via anal sex, which was a significant predictor of unprotected anal sex [adjusted odds ratio (AOR) 1.92; 95% confidence interval (95% CI), 1.16-3.16]. Other associated factors included drinking alcohol 3 or more days per week (AOR, 1.63; 95% CI, 1.05-2.54), self-report of burning urination within the past 12 months (AOR, 2.07; 95% CI, 1.14-3.76), and having never been counseled or tested for HIV (AOR, 1.66; 95% CI, 1.07-2.57). Only 21.2% of respondents correctly knew that a water-based lubricant should be used with latex condoms. Conclusions: Male sex workers who sell sex to men in Mombasa are in acute need of targeted prevention information on anal HIV and STI transmission, consistent condom use, and correct lubrication use with latex condoms. HIV programs in Africa need to consider and develop specific prevention strategies to reach this vulnerable population.