With an increase in sexual activity among young adults in Vietnam and associated risks, there is a need for evidence-based sexual health interventions. This evaluation of three sexual health programs based on the Protection Motivation Theory (PMT) was conducted in 12 communes in Ha Noi, Nha Trang City, and Ninh Hoa District. Inclusion criteria included unmarried youth 15–20 years residing in selected communes. Communes were randomly allocated to an intervention, and participants were randomly selected within each commune. The intervention programs included Vietnamese Focus on Kids (VFOK), the gender-based program Exploring the World of Adolescents (EWA), and EWA plus parental and health provider education (EWA+). Programs were delivered over a ten-week period in the communities by locally trained facilitators. The gender-based EWA program with parental involvement (EWA+) compared to VFOK showed significantly greater increase in knowledge. EWA+ in comparison to VFOK also showed significant decrease at immediate postintervention for intention to have sex. Sustained changes are observed in all three interventions for self-efficacy condom use, self-efficacy abstinence, response efficacy for condoms, extrinsic rewards, and perceived vulnerability for HIV. These findings suggest that theory-based community programs contribute to sustained changes in knowledge and attitudes regarding sexual risk among Vietnamese adolescents.