In this study a matched intervention-control site design in 14 urban health centers with random selection of 160 participants (80 in each of intervention and control) was used to evaluate a sex education program in Iran. Qualitative methods were used in a needs assessment that also set the content and method of delivery of the program. The intervention consisted of training health providers to deliver a short educational program to female clients. Evaluation questionnaires were completed before and six weeks after the intervention. Analysis of the data showed no significant difference in demographic characteristics of the study and control groups. The program demonstrated a statistically significant impact on knowledge and attitudes. There was also a statistically significant change in intentions and behavior. This study showed that even in societies where people's religious and cultural background and strict rules and laws might seem to make sexual education an impossible task, choosing the location and target population based on cultural norms, and the educational content based on the target group's needs and cultural and religious background, can pave the road to success. (Contains 4 tables and 1 note.)