Physical activity is associated with an antidepressant effect in clinical depression. Self-efficacy is one mechanism proposed to explain this effect. In this study we compared the changes in mood following exercise sessions with high and stable self-efficacy (stationary bike exercise) to exercise sessions with initially low but increasing self-efficacy (martial arts). The experimental design incorporated repeated measures and counter-balancing. Twelve clinically depressed participants completed 45-min exercise sessions consisting of stationary bike use and martial arts. A waiting control condition of 30 minutes was conducted before each exercise session. During martial arts, statistically significant increases in positive affect, reductions in negative affect and state anxiety, and increased self-efficacy were observed. During the stationary bike exercise no statistically significant changes were found. The results indicate that an increase in self-efficacy may be important for mood benefits to occur.