OBJECTIVE: Voluntary Counseling and Testing for HIV (VCT) and increasing access to male condoms are common strategies to respond to the HIV/AIDS pandemic. Using biological and behavioral outcomes, we compared programs to increase access to VCT, male condoms or both among youth in Western Kenya with the standard available HIV prevention services within this setting. DESIGN: A four arm, unblinded randomized controlled trial. METHODS: The sample includes 10,245 youth aged 17 to 24 randomly assigned to receive community-based VCT, 150 male condoms, both VCT and condoms, or neither program. All had access to standard HIV services available within their communities. Surveys and blood samples for HSV-2 testing were collected at baseline (2009-2010) and at follow up (2011-2013). VCT was offered to all participants at follow up. HSV-2 prevalence, the primary outcome, was assessed using weighted logistic regressions in an intention-to-treat analysis. RESULTS: For the 7,565 respondents surveyed at follow up, (effective tracking rate = 91%), the weighted HSV-2 prevalence was similar across groups (control group = 10.8%, condoms only group = 9.1%, VCT only group = 10.2%, VCT and condoms group = 11.5%). None of the interventions significantly reduced HSV-2 prevalence; the adjusted odds ratios were 0.87 (95% CI: 0.61-1.25) for condoms only, 0.94 (95% CI: 0.64-1.38) for VCT only, and 1.12 (95% CI: 0.79-1.58) for both interventions. The VCT intervention significantly increased HIV testing (adj OR: 3.54, 95% CI: 2.32-5.41 for VCT only, and adj OR: 5.52, 95% CI: 3.90-7.81 for condoms and VCT group). There were no statistically significant effects on risk of HIV, or on other behavioral or knowledge outcomes including self-reported pregnancy rates. CONCLUSION: This study suggests that systematic community-based VCT campaigns (in addition to VCT availability at local health clinics) and condom distribution are unlikely on their own to significantly reduce the prevalence of HSV-2 among youth.