Excess weight and obesity are major risk factors for many chronic diseases, and weight-loss interventions often include systematic exercise and nutritional supplements. The purpose of this study was to determine the independent/synergistic effects of Arthrospira (Spirulina) maxima supplementation (six weeks, 4.5 g·day−1) and a systematic physical exercise program (six weeks, twice weekly) on the body composition and cardiorespiratory fitness of overweight and obese subjects. To achieve this, 27 overweight and 25 obese sedentary male subjects were assigned to four interventions through a randomized double-blind, crossover controlled trial: A physical exercise program, with (SE) or without (Ex) Spirulina maxima; or no-exercise program, with (Sm) and without (C) Spirulina maxima. The body composition and cardiorespiratory fitness parameters were taken during a maximum intensity test. As compared to the C group, the body fat percentage of the SE, Sm and Ex groups was reduced (p < 0.05), while their maximal oxygen uptake improved (r = −0.40), and obese subjects benefited more significantly. Weight loss, the time to reach fatigue and the onset of blood lactate accumulation were improved in both of the Spirulina maxima supplemented groups, regardless of the subjects’ body weight. Spirulina maxima supplementation synergistically improves the effects of systematic exercise on body composition and cardiorespiratory fitness parameters in overweight, but mostly in individuals with obesity. Trial registration: Clinical Trials, NCT02837666. Registered 19 July 2016.