To evaluate whether determinants of consistent condom use vary by partner type among young sexually active Kenyan men, we conducted a cross-sectional assessment of lifetime sexual histories from a sub-sample of men enrolled in a clinical trial of male circumcision. 7913 partnerships of 1370 men were analyzed. 262 men (19%) reported never, 1018 (74%) sometimes and 92 (7%) always using a condom with their partners. Condoms were always used in 2672 (34%) of the total relationships-212 (70%) of the relationships with sex workers, 1643 (40%) of the casual and 817 (23%) of the regular/marital relationships. Factors influencing condom use varied significantly by partner type, suggesting that HIV prevention messages promoting condom use with higher-risk partners have achieved a moderate level of acceptance. However, in populations of young, single men in generalized epidemic settings, interventions should promote consistent condom use in all sexual encounters, independently of partner type and characteristics.