Background: The high prevalence of physical inactivity has led to a search for novel and feasible interventions that will enhance physical activity, especially among the least physically active individuals. This randomized controlled trial aimed to determine the effectiveness of a value-based intervention to promote a physically more active lifestyle among physically inactive adults. The framework of the study was based on Acceptance and Commitment Therapy (ACT). Methods: Physically inactive participants aged 30 to 50 years (n = 138) were randomly allocated to a feedback (FB, n = 69) or an acceptance- and commitment-based group (ACT + FB, n = 69). Both groups received written feedback about their objectively measured physical activity and were offered a body composition analysis. In addition, the participants in the ACT + FB group attended six group sessions and were given a pedometer for self-monitoring their physical activity during the nine-week intervention. The primary outcome was physical activity. In addition, participants’ cognitions related to exercise and physical activity were evaluated at baseline and at three- and six-month follow-ups. The changes in mean physical activity level were analysed using multilevel random regression and rank order stability, using the structural equation model. Results: Participants in both groups increased their objectively measured and self-reported physical activity with high individual differences. No difference was observed in the change of physical activity level between the FB and ACT + FB groups over time. However, the cognitions related to physical activity and exercise improved more in the ACT + FB group than in the FB group. In addition, after re-analyzing the data among the non-depressive participants, higher stability was observed in objectively measured physical activity at the individual level between the three- and six-month follow-ups in the ACT + FB group as compared to FB group. Conclusions: Acceptance- and commitment-based group intervention, combined with the self-monitoring of physical activity, was beneficial in supporting the cognition related to exercise and physical activity, and brought more stability to the individual level physical activity behaviour change, especially among the non-depressive participants.