Our study examined the effect of 8 weeks of high-intensity interval training (HIIT) and spirulina supplementation on the humoral immunity, cardio-respiratory fitness, and body composition of overweight and obese women. Thirty sedentary women (height: 161.7 ± 2.8 cm, body mass: 75.8 ± 8.4 kg, body mass index [BMI]: 28.8 ± 2.5 kg/m2, age: 25.1 ± 6.7 years) were divided into three groups: placebo with HIIT group, spirulina group (SG), or combined group (CG). Exercise groups performed HIIT for 8 weeks, with three sessions per week and four to seven repetitions in each session of 30 s running and 30 s walking; the intensity was established at 90% of the maximum heart rate. Supplementation groups received 6 g of spirulina powder per day. Fasting blood samples were collected before and after 8 weeks to determine the concentrations of immunoglobulins (IgA and IgG). There was a significant group-by-time interaction for fat free mass (FFM; p = 0.001, f = 8.52, ηp2 = 0.39) and IgA (p = 0.036, f = 3.86, ηp2 = 0.22). The post hoc analysis revealed that CG reduced FFM significantly (p = 0.012, g = −0.55) after training. CG and SG showed significantly greater IgA concentrations after 8 weeks (p = 0.02, g = 0.70 and p = 0.001, g = 0.34, respectively). We conclude that spirulina supplementation with HIIT affects the body composition (lower FFM) but also boosts IgA, which plays an important role in the immune system.