Women’s perceptions of male circumcision (MC) have implications for behavioral risk compensation, demand, and the impact of MC programs on women’s health. This mixed methods study combines data from the first two rounds of a longitudinal study (n = 934) and in-depth interviews with a subsample of respondents (n = 45) between rounds. Most women correctly reported that MC reduces men’s risk of HIV (64% R1, 82% R2). However, 30% of women at R1, and significantly more (41%) at R2, incorrectly believed MC is fully protective for men against HIV. Women also greatly overestimated the protection MC offers against STIs. The proportion of women who believed MC reduces a woman’s HIV risk if she has sex with a man who is circumcised increased significantly (50% to 70%). Qualitative data elaborate women’s misperception regarding MC. Programs should address women’s informational needs and continue to emphasize that condoms remain critical, regardless of male partner’s circumcision status.