Exercise can be used to treat depression but there is a lack of evidence regarding the optimal intensity and mode. Our aim was to compare the effects of different exercise intensities on post-treatment depression severity. People aged 18–67 years with mild to moderate depression (Patient Health Questionnaire-9 score of ≥ 10) participated in a single-blind, parallel randomized control trial lasting 12-weeks (Sweden 2011–2013). Four treatment arms were included: treatment as usual (TAU) (n = 310), light exercise (yoga or similar n = 106), moderate exercise (aerobic conditioning, n = 105) and vigorous exercise (aerobic conditioning, n = 99). Depression severity was measured at baseline and post-treatment using the Montgomery-Åsberg Depression Rating Scale (MADRS). Differences between the groups in depression severity at post-treatment were analysed using linear regression. Differences in exercise intensity were confirmed by heart rate monitoring. At post-treatment, the light (− 4.05 Confidence Interval (CI) = − 5.94, − 2.17), moderate (− 2.08 CI = − 3.98, − 0.18) and vigorous exercise groups (− 3.13 CI = − 5.07, − 1.19) had reduced their MADRS scores significantly more than TAU. No significant differences were found between the exercise groups, and no significant interaction effect was observed between group and gender. In conclusion, exercise, whether performed at a low (yoga or similar), moderate or vigorous intensity (aerobic training) is effective in treating mild to moderate depression and is at least as effective as treatment as usual by a physician.