Background: This study's aims were to compare the efficacy and negative effects of guided Internet-based cognitive behavior therapy (iCBT) and online psychoeducation (OPE) in people with major depression. Methods: A total of 131 individuals were randomized. Assessments took place at baseline (T1), six weeks (T2), and three months (T3). The primary endpoint was change in observer-based depression severity from T1 to T2. Potential negative effects were analyzed in terms of suicidal ideations, symptom deterioration, attitudes toward seeking further help, and other adverse events. Results: iCBT (n = 65) and OPE (n = 66) both reduced depressive symptoms from T1 to T2, with large changes observed for iCBT and medium for OPE (iCBT: Cohen's d = 1.09; OPE: d = 0.60). Differences between groups were significant at the primary endpoint (d = 0.36, p = 0.028). OPE continued to have a positive effect from post-treatment to follow-up, while the effect of iCBT remained stable, with differences between groups not being significant anymore at follow-up. Participants who had undergone prior psychotherapy benefited from both treatments; but for those without prior psychotherapy, iCBT was superior also at follow-up. In the iCBT group 26.2% of the participants reported at least one side-effect. Limitations: The history of psychotherapy was imbalanced between the groups. Some negative effects were assessed in the iCBT group only. Conclusions: Both iCBT and OPE were effective in reducing depressive symptoms, but with iCBT having a more rapid effect. iCBT was specifically superior in those with no prior history of psychotherapy. Negative effects occurred frequently and should be considered when implementing iCBT. Trial registration: German clinical trials register: DRKS00005025