Fasting enhances the beneficial metabolic outcomes of exercise; however, it is unknown whether body composition is favorably modified on the short term. A baseline–follow-up study was carried out to assess the effect of an established protocol involving short-term combined exercise with fasting on body composition. One hundred seven recreationally exercising males underwent a 10-day intervention across 15 fitness centers in the Netherlands involving a 3-day gradual decrease of food intake, a 3-day period with extremely low caloric intake, and a gradual 4-day increase to initial caloric intake, with daily 30-min submaximal cycling. Using dual-energy X-ray absorptiometry analysis, all subjects substantially lost total body mass (−3.9 ± 1.9 kg; p < .001) and fat mass (−3.3 ± 1.3 kg; p < .001). Average lean mass was lost (−0.6 ± 1.5 kg; p < .001), but lean mass as a percentage of total body mass was not reduced. The authors observed a loss of −3.9 ± 1.9% android fat over total fat mass (p < .001), a loss of −2.2 ± 1.9% gynoid over total fat mass (p < .001), and reduced android/gynoid ratios (−0.05 ± 0.1; p < .001). Analyzing 15 preselected single-nucleotide polymorphisms in 13 metabolism-related genes revealed trending associations for thyroid state–related single-nucleotide polymorphisms rs225014 (deiodinase 2) and rs35767 (insulin-like growth factor1), and rs1053049 (PPARD). In conclusion, a short period of combined fasting and exercise leads to a substantial loss of body and fat mass without a loss of lean mass as a percentage of total mass.