Background: Male circumcision has been shown to reduce the transmission of HIV from women to men through vaginal sex by approximately 60%. There is concern that men may engage in risk compensation after becoming circumcised, diminishing the benefits of male circumcision. Methods and Findings: We conducted qualitative interviews with 30 sexually active circumcised men in Kisumu, Kenya from March to November 2008. Most respondents reported no behavior change or increasing protective sexual behaviors including increasing condom use and reducing the number of sexual partners. A minority of men reported engaging in higher risk behaviors either not using condoms or increasing the number of sex partners. Circumcised respondents described being able to perform more rounds of sex, easier condom use, and fewer cuts on the penis during sex. Conclusions: Results illustrate that information about MC’s protection against HIV has disseminated into the larger community and MC accompanied by counseling and HIV testing can foster positive behavior change and maintain sexual behavior.