To examine the quality of evidence for exercise in the treatment of major depression, comparing specific study types; aerobic exercise vs. antidepressants, aerobic exercise vs. any physical activity, and aerobic exercise as augmentation therapy to treatment as usual vs. treatment as usual. Electronic searches for randomized controlled studies, reporting on treatment outcome in adults with major depression confirmed by a clinical interview. Quality of evidence was assessed using the Grading and Recommendations Assessment, Development and Evaluation and an additional risk of bias-protocol. Fourteen eligible studies were retrieved, of which nine had low risk of bias. We found moderate quality of evidence that aerobic exercise has no significant effect compared to antidepressants. We found moderate quality of evidence that aerobic exercise at a moderate to high intensity has no significant effect compared to other forms of physical activity. We found low quality of evidence that exercise as augmentation to treatment as usual has a small effect - depression scores were on average 0.44 of a standard deviation lower - compared to treatment as usual. In general, exercise appears to be beneficial in the treatment of depression when used in combination with medication. A significant issue that is not well addressed in previous studies is the risks associated with exercise. Further, this review indicates that aerobic exercise is not more effective than other types of physical activity, pointing to a need to further investigate active components.