This study investigated the effects of endurance followed by strength training (ES, men n = 16; women n = 15), the reverse exercise order (SE, men n = 18, women n = 13) and concurrent endurance and strength training performed on alternating days (AD, men n = 21, women n = 18) on cardiorespiratory parameters. Peak oxygen consumption (V_ O2peak) and oxygen consumption at sub-maximal power outputs (V_ O2submax) of 50 to 175 Watts in men and 50 to 125 Watts in women were assessed during an incremental cycling test both before and after 24 weeks of training. Increases in V_ O2peak in both men and women were statistically larger in AD (18±9% and 25±11%) compared to ES (7±9% and 12±12%, p = 0.002 and 0.009, respectively) and SE (7±9% and 10±8%, p = 0.005 and 0.008, respectively). No statistical group interaction was observed for V_ O2submax in men, but in women V_ O2submax was statistically lower at week 24 in ES compared to AD at 75 W (-2±6% vs. +3±6%, p = 0.027) and 125 W (-4±5% vs. +2±5%, p = 0.010). These findings indicate that endurance and strength training performed on alternating days may optimize the adaptations in V_ O2peak in both sexes, while performing ES training in women may optimize cardiorespiratory fitness at sub-maximal power outputs.