Background: Research on the effectiveness of treatments for subthreshold depression (sD) is still scarce. The aim of the study was to evaluate the efficacy of a web-based guided self-help intervention (GET.ON Mood Enhancer) in the treatment of sD. Methods: Participants with sD (n = 406) recruited from the general population via a large health insurance company were randomly allocated to a web-based cognitive behavioural intervention or to enhanced care-as-usual. The primary outcome was the reduction in depressive symptom severity as measured with the Center for Epidemiological Studies Depression Scale at post-treatment and at 6-month follow-up. Results: Participants in the intervention group showed a significantly greater pre-post reduction in depressive symptom severity (d = 1.06; 95% CI: 0.86-1.27) compared to the control condition (d = 0.29; 95% CI: 0.10-0.49). The corresponding between-group effect size was d = 0.69 (95% CI: 0.49-0.89). At 6-month follow-up the effect was reduced to d = 0.28 (95% CI: 0.09-0.48) but was still statistically significant (F1, 403 = 9.240, p = 0.003). Conclusions: This study lends support to the idea that problem solving coupled with behavioural activation is an effective treatment for sD. In addition, the delivery of this intervention over the Internet might be a promising strategy for the dissemination of psychological interventions for sD on a large scale.