Introduction: This study evaluated the effect of a 12-month physical exercise intervention accompanied by a 12-month followup evaluating stress symptoms (SS), mental resources (MR) and cardiorespiratory fitness (CRF) in healthy, working adults. We hypothesized that the stress symptoms would decrease and mental resources would increase during the intervention and that these results are associated with changes in CRF. Material and methods: The study group included healthy adults (N = 371). Three hundred thirty eight participants (212 women, 126 men) were allocated in the exercise group and 33 in the control group (17 women and 16 men). For the analysis, the exercise group was divided into subgroups according to the baseline SS and MR. Stress symptoms and MR were measured using the Occupational Stress Questionnaire. Results: During the 12-month exercise intervention, SS decreased by 16% (p < 0.0001), MR increased by 8% (p < 0.0001) and CRF increased by 7% (p < 0.0001) in the exercise group, while no changes occurred in the control group (ANCOVA, p < 0.01). In the exercise group, the results (SS, MR, and CRF) remained improved during the follow-up. There was a positive correlation between the change in SS and the change in CRF (r = 0.19, p < 0.01). In the subgroup having the highest SS at baseline, SS during the intervention decreased most (26%) (ANCOVA, p < 0.0001). Conclusions: One year physical exercise intervention improved mental well-being among working adults and this was associated with an improvement in cardiorespiratory fitness. The positive changes remained after the 12-month follow-up.