Aim: The purpose of this study was to examine physical fitness and psycho-cognitive performance and their associations in young and middle-aged workers with primarily physical versus mental work demands. Subjects and methods: Healthy young and middle-aged workers (73 men, age = 33 ± 7 years; 75 women, age = 35 ± 9 years) were recruited from German small-to-medium-sized enterprises (< 250 employees) and classified into groups with primarily mental (MD) or physical demands (PD) at work. Participants were tested for cardiorespiratory fitness, trunk flexor/extensor muscular endurance, handgrip strength, balance, leg muscle power, perceived stress, cognitive performance, and work ability. Results: Ninety-four workers were allocated to the MD (53% females) and 54 to the PD (46% females) groups. The MD group showed significantly better balance, trunk extensor muscular endurance, and cognitive performance (p < 0.035, 0.35 ≤ d ≤ 0.55) and less stress compared with the PD group (p < 0.023, d = 0.38). Group-specific Spearman rank correlation analysis (rS) revealed significant small-to-medium-sized correlations between physical fitness and cognitive performance (− 0.205 ≤ rS ≤ 0.434) in the MD and PD groups. Significant small-to-medium-sized correlations were found for physical fitness and stress/work ability (0.211 ≤ rS ≤ 0.301) in the MD group only. Further, associations of trunk extensor muscular endurance and work ability were significantly higher in the MD group (rS = 0.240) compared with the PD group (rS = − 0.141; z = 2.16, p = 0.031). Conclusions: MD workers showed better physical fitness measures (balance, trunk extensor muscular endurance) and cognitive performance and lower levels of perceived stress compared with PD workers. Small-to-medium-sized associations between physical fitness and psycho-cognitive performance measures indicate that gains in physical fitness may at least partly contribute to psycho-cognitive performance and/or vice versa, particularly in MD workers.