Evidence suggests that poor mental health literacy is a key barrier to help-seeking for mental health difficulties in adolescence. Educational programs have shown positive effects on literacy, however, the evidence base remains limited and available studies have many methodological limitations. Using cluster Randomised Control Trial (RCT) methodology, the current study examines the impact of ‘HeadStrong’, a school-based educational intervention, on mental health literacy, stigma, help-seeking, psychological distress and suicidal ideation. A total of 380 students in 22 classes (clusters) from 10 non-government secondary schools was randomised to receive either HeadStrong or Personal Development, Health and Physical Education (PDHPE) classes. Participants were assessed pre- and post-intervention, and at 6-month follow-up. Literacy improved and stigma reduced in both groups at post-intervention and follow-up, relative to baseline. However, these effects were significantly greater in the HeadStrong condition. The study demonstrates the potential of HeadStrong to improve mental health literacy and reduce stigma.