The effectiveness of evidence-based programs can be compromised if the program is not implemented with fidelity. This article describes the evaluation of an online training to improve implementation fidelity to an evidence-based HIV prevention curriculum, Reducing the Risk, through online skills-based instruction and support. Educators were randomly assigned to either the online training or a self-preparation control group. The primary outcome was the proportion of lesson activities implemented completely. Measurement of the main outcome was obtained through self-report logs, which educators were asked to complete following each of the 16 lessons taught. Data were analyzed from 162 educators. The online training group reported significantly higher overall implementation fidelity compared to the standard control group with modest effect sizes (p = 0.04-0.051 and Cohen's d = 0.31-0.33). Additionally, when fidelity scores were compared for just the core activities, implementation fidelity was significantly higher for the training group compared to the control group (p = 0.023; d = 0.36). The online training group also reported significant improvements in knowledge of the curriculum and perceptions of knowledge and skills in role-play improvement (p < 0.001-0.013; d = 0.40-0.62). However, many of the other secondary outcomes analyzed were not significant. Online training with video demonstrations may be an effective way to enhance implementation fidelity in educators.