This cluster randomized controlled trial evaluated the impact of a universal mental health promotion program, the Aussie Optimism Program (AOP), on adolescent tobacco and alcohol use. Students aged 10–13 years (N = 3288) from 63 government primary schools were recruited from an urban population area in Western Australian. Schools were randomized to a usual school health curriculum control group (21 schools), an AOP group with teacher training (20 schools), or AOP with teacher training plus coaching (22 schools). The intervention was implemented in primary school Grades 6 and 7, with follow-up in secondary school Grade 8. Students completed confidential questionnaires relating to consumption of cigarettes and alcohol over the past month. The intervention program contained activities relating to social skills, social problem solving and challenging unhelpful thoughts. The intervention was associated with lower levels of alcohol use at post-test and lower levels of both alcohol and tobacco use at a 12-month secondary school follow-up, but only when AOP was implemented by teachers who received training and coaching in the program. Hence, mental health promotion programs that focus on general life skills may also impact upon health risk behaviors such as alcohol and tobacco use in young adolescents.