Background Interventions to promote mental well-being can bring benefits to the individual and to society. The Internet can facilitate the large-scale and low-cost delivery of individually targeted health promoting interventions. Objective To evaluate the effectiveness of a self-directed Internet-delivered cognitive-behavioral skills training tool in improving mental well-being in a population sample. Methods This was a randomized trial with a waiting-list control. Using advertisements on a national health portal and through its mailing list, we recruited 3070 participants aged 18 or over, resident in England, and willing to give their email address and access a fully automated Web-based intervention. The intervention (MoodGYM) consisted of 5 interactive modules that teach cognitive-behavioral principles. Participants in the intervention arm received weekly email reminders to access the intervention. The control group received access to the intervention after the trial was completed and received no specific intervention or email reminders. Outcomes were assessed by using self-completion questionnaires. The primary outcome was mental well-being measured with the Warwick-Edinburgh Mental Well-being Scale (WEMWBS). Secondary outcomes were Center for Epidemiologic Studies Depression scale (CES-D) depression scores, Generalized Anxiety Disorder 7-item scale (GAD-7) anxiety scores, EuroQol Group 5-Dimension Self-Report Questionnaire (EQ-5D) quality of life scores, physical activity, and health service use. All outcomes were measured at baseline, and at 6- and 12-week follow-ups. Results A total of 1529 (49.80%) participants completed final follow-up at 12 weeks. Retention was 73.11% (1123/1536) in the control arm and 26.47% (406/1534) in the intervention arm. No relationship between baseline measures and withdrawal could be established. The analysis of WEMWBS mental well-being scores using a linear mixed model for repeated measures showed no difference between intervention and control group at baseline (difference –0.124 points, 95% CI –0.814 to 0.566), and significant improvements for the intervention group at 6 weeks (2.542 points, 95% CI 1.693-3.390) and at 12 weeks (2.876 points, 95% CI 1.933-3.819). The model showed a highly significant (P<.001) intervention by time interaction effect. There were also significant improvements in self-rated scores of depression and anxiety. Given the high level of attrition, a sensitivity analysis with imputed missing values was undertaken that also showed a significant positive effect of the intervention. Conclusions Participants allocated to the intervention arm had an average increase of approximately 3 points on the WEMWBS scale compared to no increase for participants in the control group. Three points on this scale is approximately one-third of a standard deviation. In a low-cost automated intervention designed to shift the population distribution of mental well-being, a small difference per individual could yield a major benefit in population terms. In common with other Web-based interventions, there were high rates of attrition. Further work is needed to improve acceptability, to evaluate against placebo effect, and to disaggregate the effect on mental well-being from the effect on depression and anxiety. Trial Registration International Standard Randomised Controlled Trial Number Register ISRCTN 48134476; http://www.controlled-trials.com/ISRCTN48134476 (Archived by WebCite® at http://www.webcitation.org/6DFgW2p3Q)