Background Depressive symptoms are highly prevalent among adolescents in Western countries. However, although treatment for depressive symptoms is available, many adolescents do not seek help when they need it. Important barriers to help-seeking among adolescents include low mental health literacy and high stigma. Therefore, we have developed a game-based school program, Moving Stories, which combines mental health literacy training for depression with contact with someone with lived experience both in the digital and nondigital world. Objective The aim of this study is to conduct a first test of the effectiveness of the newly developed game-based program, Moving Stories, using a cluster randomized controlled trial. Methods A total of 185 adolescents participated, divided over 10 classes from 4 schools. Half of the classes were randomly selected to follow the Moving Stories program, whereas the other half were in the control group, where no intervention was provided. The adolescents filled out digital questionnaires at 4 time points, with questions on mental health literacy, stigma, depressive symptoms, and the program itself (before the program, after the program, 3-month follow-up, and 6-month follow-up). Using R (R Foundation for Statistical Computing), we ran linear mixed-effects models for all continuous outcome variables and generalized linear mixed-effects models for all binary outcome variables. Results Compared with the control group, participants in the Moving Stories group improved after the program in personal stigma (b=−0.53, 95% CI −1.02 to −0.03; t179.16=−2.08; P=.04). Effects on personal stigma lasted over time (3-month follow-up: b=−0.57, 95% CI −1.11 to −0.03; t174.39=−2.07; P=.04). Most adolescents in the Moving Stories group participated in the introduction (97/99, 98%) and contact session (93/99, 94%), played the game for 4 or 5 days (83/99, 83%), and indicated that they would recommend the game to their peers (90/98, 92%). Conclusions The results of this study show the potential of Moving Stories as a stigma reduction program. With changes in the program to improve its effects on mental health literacy, Moving Stories could be implemented in schools to improve help-seeking in adolescents and reduce the negative consequences and burden of depressive symptoms. Trial Registration Dutch Trial Register NTR7033; https://trialsearch.who.int/Trial2.aspx?TrialID=NTR7033 International Registered Report Identifier (IRRID) RR2-10.2196/11255