Background: Chronic inflammation associated with breast cancer (BC) poses a major challenge in care management and may be ameliorated by physical activity. This randomized controlled trial assessed the effects of a 12-week high-intensity interval training (HIIT) and moderate-intensity continuous training (MICT) on inflammatory markers, body composition, and physical fitness in BC survivors (BCS). Methods: Forty BCS (age = 57 ± 1 years; body mass [BM] = 74.8 ± 1.5 kg; VO_2peak = 20.8 ± 2.1 mL·kg⁻¹·min⁻¹) were randomly assigned to three groups: HIIT (n = 15), MICT (n = 15), or control (CON; n = 15). The intervention groups (HIIT and MICT) performed their respective exercise protocols on a cycle ergometer 3 days/week for 12 weeks while the CON group maintained their current lifestyle. Baseline and post-intervention assessments included body composition (BM, fat mass (FM), lean mass (LM)), physical fitness (VO_2peak, lower body strength (LBS), upper body strength (UBS)), and serum concentrations of tumor necrosis factor-alpha (TNF-α), interleukin-6 (IL-6), interleukin-8 (IL-8), interleukin-10 (IL-10), leptin, and adiponectin. Results: Both intervention groups significantly (p < 0.05) decreased BM (HIIT = −1.8 kg, MICT = −0.91 kg), FM (HIIT = −0.81 kg, MICT = −0.18 kg), TNF-α (HIIT = −1.84 pg/mL, MICT = −0.99 pg/mL), IL-6 (HIIT = −0.71 pg/mL, MICT = −0.36 pg/mL), leptin (HIIT = −0.35 pg/mL, MICT = −0.16 pg/mL) and increased VO_2peak (HIIT = 0.95 mL·kg⁻¹·min⁻¹, MICT = 0.67 mL·kg⁻¹·min⁻¹), LBS (HIIT = 2.84 kg, MICT = 1.53 kg), UBS (HIIT = 0.53 kg, MICT = 0.53 kg), IL-10 (HIIT = 0.63 pg/mL, MICT = 0.38 pg/mL), and adiponectin (HIIT = 0.23 ng/mL, MICT = 0.1 ng/mL) compared to baseline. The changes in BM, FM, TNF-α, leptin, and LBS were significantly greater in HIIT compared to all other groups. Conclusions: Our findings indicate that compared to the often-recommended MICT, HIIT may be a more beneficial exercise therapy for the improvement of inflammation, body composition and LBS in BCS; and consequently, merits long-term study