We examined sociodemographic characteristics, knowledge, behavior, and attitude of men who had sex with commercial sex workers (CSWs) in Kenya. About 15% of the men had sex with CSWs. Men who had two or more partners, were away from home five or more times in the past year, and used condoms consistently with their last three partners were likely to have had sex with CSWs (odds ratio [OR] = 2.70, p = .000; OR = 1.43, p = .044; OR = 2.50, p = .000, respectively). Men with better knowledge of HIV/AIDS prevention methods were likely to have had sex with CSWs (OR = 1.62, p = .004). As expected, having had sex with CSWs was associated with higher risk of sexually transmitted infection (OR = 3.62, p = .000). This unexpected association between knowledge and behavior could be bidirectional or reverse causality. Nonetheless, knowledge in prevention has not been translated to practice and change in behavior. These processes require continuous efforts, including assertive campaigns on sexual practices and behaviors.