It is important to understand how women's sexual practices may be influenced by male circumcision (MC) as an HIV prevention effort. Women's beliefs about MC and sexual behaviour will likely influence the scale-up and uptake of medical MC. We conducted qualitative interviews with 30 sexually active women in Kisumu, Kenya. Women discussed MC related to perceived health benefits, condom use, sexual behaviour, knowledge of susceptibility to HIV and sexually transmitted infections (STIs), circumcision preference, and influence on circumcision uptake. Respondents had a good understanding of the partial protection of MC for acquisition of HIV for men. Women perceived circumcised men as cleaner, carrying fewer diseases, and taking more time to reach ejaculation. Male's circumcision status is a salient factor for women's sexual decision making, including partner choice, and condom use. It will be important that educational information affirms that MC provides only partial protection against female to male transmission of HIV and some STIs; that other HIV and STI prevention methods such as condoms need to be used in conjunction with MC; that MC does not preclude a man from having HIV; and that couples should develop plans for not having sex while the man is healing.