One of the reasons for the perpetuation of female circumcision is that it controls female sexuality. In this study, the authors examined the relationship between female circumcision and the sexual behavior of women in Kenya and Nigeria. Data on women who were aware of circumcision and were circumcised were extracted from the Kenya Demographic and Health Survey of 2008–09 as well as the Nigeria Demographic and Health Survey of 2008. The sample size was 7,344 for Kenya and 16,294 for Nigeria. The outcome variables were age at first intercourse and total lifetime number of sexual partners. The study hypothesis was that women who were circumcised were less likely to have initiated sex early and to have only one sex partner. Cox proportional hazards regression and Poisson regression were used to examine the relations of female circumcision and other selected variables to sexual behavior. No association was observed between female circumcision and the outcomes for sexual behavior of women in Kenya and Nigeria. The argument of sexual chastity is insufficient to sustain the perpetuation of female circumcision.