The influence of psychological states on physiological responses during exercise is of considerable importance to individuals for which the efficiency of energy production is critical to occupational performance. Numerous studies have shown that aerobic fitness is associated with enhanced cardiovascular efficiency at rest and that responses to mental stress demonstrate evidence of increased sensitivity (relative increase in HR response) and enhanced efficiency (a decrease in absolute HR). However, the effect of aerobic fitness and its impact on cardiorespiratory (CR) responses to psychological stress during exercise has not been investigated. Therefore, the purpose of this study was three-fold; (1) to examine during exercise, anxiety, effort sense, and CR responses to a mental challenge, (2) to examine anxiety and heart rate (HR) responses from rest to exercise with mental challenge between below average fitness (Low Fit) and well-above average fitness (Hi Fit) individuals (exercising at similar relative intensities), and (3) to examine anxiety, effort sense, and CR responses of Low Fit and Hi Fit individuals to a mental challenge during exercise at a similar relative intensity. Twelve Low Fit and eleven Hi Fit subjects participated in two, 32-minute cycle ergometer rides at 65 % of V·O2max. In the mental challenge condition (MCC), subjects rode while participating in mentally challenging tasks (Stroop Color-Word task and mental arithmetic) from min 6 to min 14 of the protocol. In the no mental challenge condition (NMCC), subjects exercised at the same intensity and duration without a stressor. Subjects were counter-balanced between fitness levels and condition. HR, V·E, V·E/V·O2, RR, V·O2, RER, effort sense (RPE), and state anxiety (SAI) were assessed at 5, 14, 24, and 30 min. SAI was also assessed at - 5 min before exercise and after 15 min of recovery. In addition, the NASA task load index (NTLX) was used to assess perceived overall workload. SAI increased significantly at 14 min in the MCC. NTLX scores indicated that the MCC was perceived as a greater overall workload. Furthermore, HR, V·E, V·E/V·O2, and RR were significantly elevated during the mental challenge condition at 14 min. The Hi Fit subjects tended to respond to the dual stress of exercise and mental challenge with a relative increase in HR, while absolute HR was similar in both groups. An examination of fitness group differences revealed that SAI and NTLX were similar for Low Fit and Hi Fit subjects when exercising in the MCC, although, Hi Fit subjects demonstrated lower HR responses from 6 min to 14 min. V·E, V·E/V·O2, and RR were similar for Low Fit and Hi Fit subjects. These results suggest that psychological stress during physical activity can exacerbate cardiorespiratory responses and suggests that factors that impact CR adjustment to mental challenge from resting baseline may differ from the factors that impact CR adjustment to mental challenge during exercise. Finally, fitness level attenuates HR and may attenuate additional cardiorespiratory responses while participating in a dual stress condition, of exercise and mental challenge.