Contraception can reduce the dual burden of high fertility and high HIV prevalence in sub-Sahara Africa, but significant barriers remain regarding access and use. We describe factors associated with nonuse of contraception and with use of specific contraceptive methods in HIV positive and HIV negative Rwandan women. Data from 395 HIV-positive and 76 HIV-negative women who desired no pregnancy in the previous 6 months were analyzed using univariate and multivariate logistic regression models to identify clinical and demographic characteristics that predict contraceptive use. Differences in contraceptive methods used were dependent on marital/partner status, partner’s knowledge of a woman’s HIV status, and age. Overall, condoms, abstinence, and hormonal methods were the most used, though differences existed by HIV status. Less than 10% of women both HIV+ and HIV− used no contraception. Important differences exist between HIV-positive and HIV-negative women with regard to contraceptive method use that should be addressed by interventions seeking to improve contraceptive prevalence.