Despite numerous behavioral interventions designed for women, rates of HIV and STIs are increasing. Interventions are needed that reach a large number of at-risk individuals. This study was a randomized clinical trial of a HIV/STI behavioral intervention conducted in Baltimore, MD, USA. Heterosexual women (n = 169) completed a baseline and three semiannual follow-up visits. Participants were randomized into a standard of care comparison condition or a Peer Mentor condition. At the 6-month follow-up, Peer Mentors were less likely to have multiple sex partners [AOR: 0.28 (95% CI: 0.13, 0.63)]. At the 18 month follow-up assessment, Peer Mentors increased their condom use during vaginal [AOR: 0.47 (95% CI: 0.25, 0.87)] and anal sex [AOR: 0.24 (95% CI: 0.09, 0.68)] as well as with main [AOR: 0.41 (95% CI: 0.21, 0.77)] and non-main partners [AOR: 0.33 (95% CI: 0.14, 0.79)]. Peer education is a sustainable approach to change risky sexual behaviors.