Background: Self-help therapies are often effective in reducing mental health problems. We developed a new Web-based self-help intervention based on problem-solving therapy, which may be used for people with different types of comorbid problems: depression, anxiety, and work-related stress. Objective: The aim was to study whether a Web-based self-help intervention is effective in reducing depression, anxiety, and work-related stress (burnout). Methods: A total of 213 participants were recruited through mass media and randomized to the intervention (n = 107) or a waiting list control group (n = 106). The Web-based course took 4 weeks. Every week an automated email was sent to the participants to explain the contents and exercises for the coming week. In addition, participants were supported by trained psychology students who offered feedback by email on the completed exercises. The core element of the intervention is a procedure in which the participants learn to approach solvable problems in a structured way. At pre-test and post-test, we measured the following primary outcomes: depression (CES-D and MDI), anxiety (SCL-A and HADS), and work-related stress (MBI). Quality of life (EQ-5D) was measured as a secondary outcome. Intention-to-treat analyses were performed. Results: Of the 213 participants, 177 (83.1%) completed the baseline and follow-up questionnaires; missing data were statistically imputed. Of all 107 participants in the intervention group, 9% (n = 10) dropped out before the course started and 55% (n = 59) completed the whole course. Among all participants, the intervention was effective in reducing symptoms of depression (CES-D: Cohen's d = 0.50, 95% confidence interval (CI) 0.22-0.79; MDI: d = 0.33, 95% CI 0.03-0.63) and anxiety (SCL-A: d = 0.42, 95% CI 0.14-0.70; HADS: d = 0.33, 95% CI 0.04-0.61) as well as in enhancing quality of life (d = 0.31, 95% CI 0.03-0.60). Moreover, a higher percentage of patients in the intervention group experienced a significant improvement in symptoms (CES-D: odds ratio [OR] = 3.5, 95% CI 1.9-6.7; MDI: OR = 3.7, 95% CI 1.4-10.0; SCL-A: OR = 2.1, 95% CI 1.0-4.6; HADS: OR = 3.1, 95% CI 1.6-6.0). Patients in the intervention group also recovered more often (MDI: OR = 2.2; SCL-A: OR = 2.0; HADS < 8), although these results were not statistically significant. The course was less effective for work-related stress, but participants in the intervention group recovered more often from burnout than those in the control group (OR = 4.0, 95% CI 1.2-13.5). Conclusions: We demonstrated statistically and clinically significant effects on symptoms of depression and anxiety. These effects were even more pronounced among participants with more severe baseline problems and for participants who fully completed the course. The effects on work-related stress and quality of life were less clear. To our knowledge, this is the first trial of a Web-based, problem-solving intervention for people with different types of (comorbid) emotional problems. The results are promising, especially for symptoms of depression and anxiety. Further research is needed to enhance the effectiveness for work-related stress. Trial Registration: International Standard Randomized Controlled Trial Number (ISRCTN) 14881571.