Background: Polycystic ovary syndrome (PCOS) and metabolic inflexibility are linked to insulin resistance, and women with PCOS appear to be metabolic inflexible in the rested, insulin-stimulated state. Exercise training is a primary lifestyle intervention in PCOS. Exercise training improves whole-body fat oxidation during submaximal exercise in healthy women, yet little is known about the effect on this outcome in women with PCOS. Methods: We measured whole-body fat oxidation rates during sub maximal exercise before and after 16 weeks of high-intensity interval training (HIT) in women with PCOS randomly allocated to either: low- or high-volume HIT (n = 41; low-volume HIT, 10 × 1 min work bouts at maximal, sustainable intensity and high-volume HIT, 4 × 4 min work bouts at 90–95% of maximal heart rate) or non-exercise control (n = 23), and in women without PCOS (Non-PCOS) allocated to low- or high volume HIT (n = 15). HIT was undertaken three times weekly. In a subset of women with and without PCOS, we measured mitochondrial respiration in abdominal and gluteal subcutaneous adipose tissue using high-resolution respirometry, as well as fat cell sizes in these tissues. Results: At baseline, women with PCOS had lower whole-body fat oxidation and mitochondrial respiration rates in abdominal adipose tissue compared to Non-PCOS. Peak oxygen uptake (mL/min/kg) increased in women with PCOS (~4%, p = 0.006) and Non-PCOS (~6%, p = 0.003) after 16 weeks of HIT. Whole-body fat oxidation only improved in Non-PCOS after HIT. No changes were observed in mitochondrial respiration and cell size in abdominal and gluteal adipose tissue after HIT in either group of women. Conclusion: We observed exercise-induced improvements in whole-body fat oxidation during submaximal exercise in Non-PCOS, but not in women with PCOS, after 16 weeks of HIT, suggesting metabolic inflexibility in women with PCOS. Clinical Trial Registration: www.clinicaltrials.gov, identifier NCT02419482 and NCT02943291.