We examined the efficacy of a brief behavioral intervention to promote condom use among female sex workers in Tijuana and Ciudad Juarez, Mexico. We randomized 924 female sex workers 18 years or older without known HIV infection living in Tijuana and Ciudad Juarez who had recently had unprotected sex with clients to a 30-minute behavioral intervention or a didactic control condition. At baseline and 6 months, women underwent interviews and testing for HIV, syphilis, gonorrhea, and chlamydia. We observed a 40% decline in cumulative sexually transmitted illness incidence (P = .049) in the intervention group. Incidence density for the intervention versus control groups was 13.8 versus 24.92 per 100 person-years for sexually transmitted illnesses combined (P = .034) and 0 versus 2.01 per 100 person-years for HIV (P < .001). There were concomitant increases in the number and percentage of protected sex acts and decreases in the number of unprotected sex acts with clients (P < .05). This brief behavioral intervention shows promise in reducing HIV and sexually transmitted illness risk behaviors among female sex workers and may be transferable to other resource-constrained settings.