This study aimed to investigate the association between mental health and comprehensive workplace health promotion (WHP) delivered to an entire state public service workforce (~28,000 employees) over a three-year period. Government departments in a state public service were supported to design and deliver a comprehensive, multi-component health promotion program, Healthy@Work, which targeted modifiable health risks including unhealthy lifestyles and stress. Repeated cross-sectional surveys compared self-reported psychological distress (Kessler-10; K10) at commencement (N = 3406) and after 3 years (N = 3228). WHP availability and participation over time was assessed, and associations between the K10 and exposure to programs estimated. Analyses were repeated for a cohort subgroup (N = 580). Data were weighted for non-response. Participation in any mental health and lifestyle programs approximately doubled after 3 years. Both male and female employees with poorer mental health participated more often over time. Women’s psychological distress decreased over time but this change was only partially attributable to participation in WHP, and only to lifestyle interventions. Average psychological distress did not change over time for men. Unexpectedly, program components directly targeting mental health were not associated with distress for either men or women. Cohort results corroborated findings. Healthy@Work was successful in increasing participation across a range of program types, including for men and women with poorer mental health. A small positive association of participation in lifestyle programs with mental health was observed for women but not men. The lack of association of mental health programs may have reflected program quality, its universality of application or other contextual factors.