Background: There has been increasing evidence that exercise therapy is effective in the treatment and prevention of major depression (MD). However, the basic molecular mechanisms underlying the effects of exercise on MD remain unclear. We conducted a preliminary study to clarify the effect of exercise therapy on MD, focusing on the dynamics of nitric oxide (NO) and catecholamine metabolites, which have been found to be associated with MD. Methods: Eleven outpatients with mild to moderate MD and 37 healthy controls (HC) were included in the study. The participants’ clinical records and questionnaires were screened for their past medical history. For their exercise therapy, the participants were instructed to walk the equivalent of 17.5 kcal/kg/week for 8 weeks. Blood samples were collected from all participants at baseline, 4 weeks, and 8 weeks after the start of exercise therapy, and plasma metabolites of NO (NOx), homovanillic acid (HVA), and 3-methoxy-4-hydroxyphenylglycol (MHPG) were analyzed. We also assessed the 17-item Hamilton Rating Scale for Depression (HRSD-17) in patients with MD. A mixed-effects regression model was used to compare the mean values by time (baseline, 4, and 8 weeks) for the three corresponding groups (NOx, MHPG, and HVA). Results: HRSD-17 scores decreased significantly in the MD group after 8 weeks of exercise therapy. NOx and MHPG increased, but there was no significant change in HVA in the MD group after the exercise therapy. NOx decreased after exercise, and HVA increased significantly from baseline after 4 weeks of exercise but decreased after 8 weeks of exercise in the HC group. Conclusions: The effects of exercise on NOx, MHPG, and HVA may differ between MD and HC. The potential mechanisms for the benefits of walking exercise in MD patients will be the subject for future research.