INTRODUCTION: Psychological stress is associated with sedentary behavior, which may impair exercise performance. The aim of our study was to examine the association between psychological stress and physical fitness in military personnel. METHOD: A military cohort of 4080 subjects in Taiwan was used for the analysis. The Brief Symptoms Rating Scale (BSRS-5) includes items of anxiety, depression, hostility, interpersonal sensitivity, and insomnia measured by a five-point Likert-type scale of 0-4. Psychological stress was defined as normal (n = 3657), slight (n = 314), and great (n = 109) by BSRS-5 score ≤5, 6-9, and ≥10, respectively. Aerobic fitness and anaerobic fitness were evaluated by the time of 3000-meter running and the numbers of 2-min sit-ups and 2-min push-ups, respectively. Multiple linear and logistic regression analyses were used to determine the relationship. RESULTS: As compared with normal stress, slight and great stress were positive dose-dependently correlated with 3000-meter running time (β = 9.09 and 14.44; P = 0.0032 and 0.048, respectively) after adjusting for age, sex, service specialty, body mass index, systolic blood pressure, cigarette smoking, alcohol intake, hemoglobin levels, and exercise frequency. Similarly, those with slight stress were more likely to be the worst 10% performers in the 3000-meter run test relative to the normal individuals (odds ratio and 95% confidence intervals: 1.50, 1.00-2.24). By contrast, there was no relationship of psychological stress with the numbers of 2-min sit-ups and 2-min push-ups. CONCLUSIONS: Our findings suggest that the presence of higher psychological stress on military personnel may reduce their cardiorespiratory fitness but not affect the anaerobic fitness.