Objectives: This study's objective was to assess the effects of a 12-month physical exercise intervention on work ability (WAI) and cardiorespiratory fitness (CRF) in healthy working adults. Methods: The study group had 371 participants, of which 338 (212 women and 126 men) were allocated in the exercise group and 33 (17 women and 16 men) in the control group. The exercise group underwent a 12-month exercise program followed by a 12-month follow-up. WAI and CRF were evaluated at baseline, and at 4, 8, 12, and 24 study months, in both exercise and control groups. The exercise group was divided into subgroups according to baseline WAI classifications (poor/moderate, good, excellent). Results: During the 12-month exercise intervention, the exercise group increased their leisure-time physical activity by 71% (p = 0.016) and improved the mean WAI by 3% and CRF by 7% (p < 0.0001, in both), while WAI and CRF decreased in the control group (ANCOVA using age, sex and BMI as covariates, for WAI, p = 0.013 and for CRF, p = 0.008). The changes in WAI and CRF between the exercise group and control group were significantly different during the intervention (baseline vs. 12-months, p = 0.028 and p = 0.007) and after the follow-up (p = 0.001 and p = 0.040), respectively. A light positive correlation between the changes in WAI and in CRF (r = 0.19, p < 0.01) existed. WAI improvement was the highest (13%, p < 0.0001) in the subgroup having poor/moderate WAI at baseline (ANCOVA, p < 0.001). Conclusions: The improvement of WAI associated with CRF. These results suggest that a physical exercise intervention may improve work ability.