(1) Background: Evidence suggests that aerobic exercise and high-intensity interval training (HIIT) might increase fat oxidation and reduce fat. However, limited research has examined the effects of combining progressive aerobic exercise and HIIT interventions in sedentary adults with overweight and obesity, and differences in its effects between men and women remain unclear. The purpose of this study was to investigate the effects of combined progressive aerobic exercise and HIIT (CAEH) on fat oxidation and fat reduction in sedentary Chinese adults and compare sex differences in sedentary adults after seven weeks. (2) Methods: Eighty-four sedentary obese adults were enrolled and allocated to two groups in baseline (experimental (EXP) group:42; control (CON) group:42), and fifty-six subjects (EXP:31; CON:25) completed the experiments and were included in the final analysis. Subjects in the EXP group performed CAEH three times per week for seven weeks. Subjects in the CON group were advised to continue with their normal daily activities. Anthropometric, lipid profile, cardiorespiratory fitness, and fat oxidation outcomes were assessed before and after the intervention. (3) Results: After seven weeks of the CAEH intervention, compared with the CON group, the EXP group showed significant increases in fat oxidation at rest (FO_rest) (+0.03 g/min, p < 0.01), maximal fat oxidation (MFO) (+0.05 g/min, p < 0.01), and maximal oxygen intake (VO2max) (+3.2 mL/kg/min, p < 0.01). The changes in the percentages of the FO_rest (+57%) and the VO2max (+16%) were significantly greater (+20%, +6%) in males than in females (p < 0.05, p < 0.05). The body mass index (BMI) (−1.2 kg/m2, p < 0.01), body fat percentage (−3.2%, p < 0.001), visceral fat area (−12.8 cm2, p < 0.001), and total cholesterol (TC) levels (−0.4 mmol/L, p < 0.05) were significantly decreased in the EXP group. (4) Conclusions: Seven weeks of the CAEH intervention effectively improved FO_rest, MFO, and VO2max in sedentary obese adults, and the improvements in FO_rest and VO2max were more pronounced in males than in females. CAEH also improved body composition and TC levels in sedentary obese adults