Purpose: The aim of this research was to assess the association between university-based instructional physical activity (PA) courses and changes in overall PA levels and negative mood and their interrelations. The study also sought to determine the amount of change in PA required to significantly improve mood in course enrollees. Method: Participants were university students initially completing PA below the level recommended for health who were either presently enrolled in an elective instructional PA course (treatment group, n = 52, 69% female) or not presently enrolled in such a course (comparison group, n = 32, 69% female). Validated surveys assessed volumes of PA completed per week and overall negative mood from baseline to course end. Mediation analyses assessed group effects on mood through PA changes and reciprocal relations between PA and mood changes. Results: There was a significantly greater increase in PA and significantly more reduction in negative mood in the treatment group. Change in PA completely mediated the relationship between group and change in negative mood, and change in mood completely mediated the relationship between group and PA. These findings indicated a reciprocal, mutually reinforcing relationship between changes in PA and mood. An increase in PA of at least 2 days/week was associated with a significant reduction in negative mood, with no greater effect for more increase. Conclusions: Results provided an improved understanding of the effects of university-based instructional PA courses and how they might be leveraged to improve students’ mental health and possibly contribute to their academic success.