Background: Prevention of depression is important due to the substantial burden of disease associated with it. To this end, we developed a novel, brief, and low-threshold Web-based self-help approach for depressive complaints called complaint-directed mini-interventions (CDMIs). These CDMIs focus on highly prevalent complaints that are demonstrably associated with depression and have a substantial economic impact: stress, sleep problems, and worry. Objective: The aim was to evaluate the effectiveness of the Web-based self-help CDMIs in a sample of adults with mild-to-moderate depressive symptoms compared to a wait-list control group. Methods: A two-armed randomized controlled trial was conducted. An open recruitment strategy was used. Participants were randomized to either the Web-based CDMIs or the no-intervention wait-list control group. The CDMIs are online, unguided, self-help interventions, largely based on cognitive behavioral techniques, which consist of 3 to 4 modules with up to 6 exercises per module. Participants are free to choose between the modules and exercises. Assessments, using self-report questionnaires, took place at baseline and at 3 and 6 months after baseline. The control group was given access to the intervention following the 3-month assessment. The primary goal of the CDMIs is to reduce depressive complaints. The primary outcome of the study was a reduction in depressive complaints as measured by the Inventory of Depressive Symptomatology Self-Report (IDS-SR). Secondary outcomes included reductions in stress, worry, sleep problems, and anxiety complaints, and improvements in well-being. Data were analyzed using linear mixed models. Results: In total, 329 participants enrolled in the trial, of which 165 were randomized to the intervention group and 164 to the control group. Approximately three-quarters of the intervention group actually created an account. Of these participants, 91.3% (116/127) logged into their chosen CDMI at least once during the 3-month intervention period (median 3, range 0-166). After 3 months, there was a significant reduction in depressive symptomatology for participants in the intervention group compared to participants in the wait-list control group (reduction in depression: mean -4.47, 95% CI -6.54 to -2.40; Cohen d=-0.70). Furthermore, significant effects were observed for sleep problems, worry, anxiety, and well-being, with effect sizes ranging from -0.29 to -0.40. The intervention did not significantly reduce stress. At 6-month follow-up, the improvements in the intervention group were generally sustained. Conclusions: This study shows that the online self-help CDMIs have a positive impact on various mental health outcomes. Future research should focus on which specific strategies may boost adherence, and increase the reach of the CDMIs among people with low socioeconomic status. ClinicalTrial: Netherlands Trial Register (NTR): NTR4612; http://www.trialregister.nl/trialreg/admin/rctview.asp?TC=4612 (Archived by WebCite at http://www.webcitation.org/6n4PVYddM).