Many depressed people don't receive help for their symptoms and there are various barriers that impede help-seeking. The Internet may offer interesting alternatives for reaching and helping people with depression. Depression can be treated effectively with Internet-based cognitive behavioral therapy (CBT). But a short intervention, based on problem solving therapy (PST), could constitute a worthwhile alternative for CBT. In this study we evaluated the effectiveness of Internet-based CBT and Internet-based PST in comparison to a waiting list control group (WL), and determined the differences between the two treatments. A total of 263 participants were randomized to the three conditions. The main inclusion criterion was presence of depressive symptoms (≥ 16 on the Center for Epidemiological Studies Depression scale). CBT and PST consisted of eight and five weekly lessons, respectively. Participants were supported by e-mail. Self-report measures of depression, anxiety and quality of life were filled in at pretest and after five, eight and 12 weeks. Between-group effect sizes for depressive symptoms were 0.54 for CBT after eight weeks (95% confidence interval (CI): 0.25 - 0.84) and 0.47 for PST after five weeks (95% CI: 0.17 - 0.77). These effects were further improved at 12 weeks (CBT: 0.69, 95% CI: 0.41 - 0.98; PST: 0.65, 95% CI: 0.36 - 0.95). For anxiety, effect sizes were also at a medium level. Effect sizes for quality of life were low. After 12 weeks, clinical significant change was significant higher for CBT (N = 34, 38.6%) and PST (N = 30, 34.1%) than for WL (N = 0). Both Internet-based treatments are effective in reducing depressive symptoms, although the effect of PST is realized more quickly.