The aim of this study was to investigate the association between physical activity (PA) and objective heart rate variability (HRV)-based stress and recovery with subjective stress in a longitudinal setting. Working-age participants (n = 221; 185 women, 36 men) were overweight (body mass index, 25.3–40.1 kg/m2) and psychologically distressed (≥3/12 points on the General Health Questionnaire). Objective stress and recovery were based on HRV recordings over 1–3 work days. Subjective stress was assessed with the Perceived Stress Scale and PA level with a questionnaire. Data were collected at three time points: baseline, 10 weeks post intervention, and at the 36-week follow-up. We adopted a latent growth model to investigate the initial level and change in PA, objective stress and recovery, and subjective stress at the three measurement time points. The results showed that initial levels of PA (P < 0.001) and objective stress (P = 0.001) and recovery (P < 0.01) were associated with the change in subjective stress. The results persisted after adjustment for intervention group. The present results suggest that high PA and objectively assessed low stress and good recovery have positive effects on changes in subjective stress in the long-term.