Background: Women with children are less likely to engage in adequate physical activity (PA) than women without children. This study aimed to evaluate the efficacy of two strategies for promoting increased PA among mothers of preschool-aged children, and to explore the mediators of any resulting change in PA behavior. Design: Controlled intervention trial incorporating repeated data collection from 554 women, randomized to one of three experimental conditions. Intervention Group 1 served as a control, while women in Groups 2 and 3 were given print information about overcoming PA barriers. Women in Group 3 were also invited to discuss the development of local strategies for the promotion of PA among mothers of young children. The primary strategies included increasing partner support, social advocacy, and capacity building, and were implemented through collaboration among participants, researchers, and community organizations. Main Outcome Measures: Adequate physical activity (PA), self-efficacy (SE) and partner support (PS). Results: Following the intervention, women in Group 3 were significantly more likely to meet guidelines for PA than controls (odds ratio [OR]=1.71, confidence interval [CI]=1.05-2.77)] after controlling for age and PA at baseline. After controlling for baseline PA, residualized change in SE (OR=1.86, CI=1.17-2.94) and PS (OR=2.29, CI=1.46-3.58) significantly predicted meeting guidelines. After controlling for residual change in PS and SE, the significant intervention effect was attenuated (Group 3 OR=1.40, CI=0.76-2.36), indicating that partner support and self-efficacy may be mediators of physical activity behavior change. Conclusions: The findings indicate that community participation approaches that facilitate increased self-efficacy and partner support can be effective in increasing PA among mothers of young children.