When examining the prevalence of physical inactivity by gender and age, women over the age of 25 are at an increased risk for sedentary behavior. Childbearing and motherhood have been explored as one possible explanation for this increased risk. Post natal exercise studies to date demonstrate promising physical and psychological outcomes, however few physical activity interventions have been theory-driven and tailored to post natal exercise initiates. The purpose of this study was to compare the effects of a group-mediated cognitive behavioral intervention based upon social-cognitive theory and group dynamics (GMCB) to a standard care postnatal exercise program (SE). A randomized, two-arm intervention design was used. Fifty-seven post natal women were randomized to one of two conditions: (1) a standard exercise treatment (SE) and (2) a standard exercise treatment plus group-mediated cognitive behavioral intervention (GMCB). Participants in both conditions participated in a four-week intensive phase where participants received standard exercise training. In addition, GMCB participants received self-regulatory behavioral skills training via six group-mediated counseling sessions. Following the intensive phase, participants engaged in a four-week home-based phase of self-structured exercise. Measures of physical activity, barrier efficacy, and proximal outcome expectations were administered and data were analyzed using ANCOVA procedures. ANCOVA of change scores for frequency, minutes, and volume of physical activity revealed significant treatment effects over the intensive and home-based phases (ps < 0.01). In addition, ANCOVA of change in mean barrier efficacy and proximal outcome expectations at the conclusion of the intensive phase demonstrated that GMCB participants increased their initial level of barrier efficacy and outcome expectations while SE participants decreased (p < 0.05). While both exercise programs resulted in improvements to exercise participation, the GMCB intervention produced greater improvement in overall physical activity, barrier efficacy and proximal outcome expectations.