We examine efficacy of the Parents Matter! Program (PMP), a program to teach African-American parents of preadolescents sexual communication and HIV-prevention skills, through a multicenter, randomized control trial. A total of 1115 parent-child participants were randomized to one of three intervention arms (enhanced, brief, control). Percentages and 95% confidence intervals compare parents' perception of child readiness to learn about sexual issues, communication effectiveness, and dyad concordance from baseline to 12 months postintervention. Wilcoxon rank sum tests compare the changes in scores measuring communication content in HIV/AIDS, abstinence, and condom use. Compared to control, parents in the enhanced arm increased perception of child readiness to learn about sex (16% vs. 29%; p less than 0.001), and a greater proportion of parent-child dyads reported concordant responses on communication topics: HIV/AIDS (15%, 95% CI = 8-21%; p less than 0.001), abstinence (13%, 95% CI = 7-20%; p less than 0.001), condoms (15%, 95% CI = 9-22%; p less than 0.001). Increases in communication scores in HIV/AIDS, abstinence, and condom use were greater in the enhanced arm than control (p less than 0.01). We conclude that the enhanced PMP can help parents educate children about HIV and prepare children to avoid sexual risk.