This systematic review examined the effect of exercise training interventions on physical fitness in adults with overweight or obesity and compared the effectiveness of different types of exercise training. Four electronic databases were searched. Articles were included if they described randomized controlled trials of exercise training interventions and their effect on maximal oxygen consumption or muscle strength in adults with overweight or obesity. Changes in outcome parameters were analyzed using random effects meta-analyses for different training types (aerobic, resistance, combined aerobic plus resistance, and high-intensity interval training). Eighty-eight articles satisfied the inclusion criteria of which 66 (3964 participants) could be included in the meta-analyses. All training types increased VO2max (mean difference 3.82 ml/min/kg (95% CI 3.17, 4.48), P < 0.00001; I2 = 48%). In direct comparisons, resistance training was less effective in improving VO2max than aerobic training, HIIT was slightly more effective than aerobic training, and no difference between aerobic and combined aerobic plus resistance training was found. For muscle strength benefits, incorporation of resistance exercise in the training program is indicated. Exercise training increases VO2max and muscle strength in adults with overweight or obesity. Differences between training types should be weighed with other needs and preferences when health professionals advise on exercise training to improve physical fitness.