Background: Progression diets after bariatric surgery (BS) are restricted in calories and protein, and they may induce a worsening of body composition. The aim of this study was to evaluate the effect of a modified diet with an oral nutritional supplement that is hyperproteic and normocaloric over the body composition. Methods: A two-arm ambispective observational cohort study was designed. Forty-four patients who underwent sleeve gastrectomy were included in the study. Thirty patients received a progression diet with a normocaloric, hyperproteic oral nutritional supplement during the first two weeks after surgery (820 kcal, 65.5 g protein). They were compared with a historical cohort of 14 patients treated with a standard progression diet (220 kcal, 11.5 g protein). Anthropometric and body composition (using electrical bioimpedanciometry) data were analyzed before BS and 1 month after the surgery. Results: The mean age was 47.35(10.22) years; 75% were women, and the average presurgical body mass index (BMI) was 45.98(6.13) kg/m2, with no differences between both arms of intervention. One month after surgery, no differences in the percentage of excess weight loss (%PEWL) were observed between patients in the high-protein-diet group (HP) and low-protein-diet group (LP) (HP: 21.86 (12.60)%; LP: 18.10 (13.49)%; p = 0.38). A lower loss of appendicular skeletal muscle mass index was observed in the HP (HP: −5.70 (8.79)%; LP: −10.54 (6.29)%; p < 0.05) and fat-free mass index (HP: 3.86 (8.50)%; LP:−9.44 (5.75)%; p = 0.03), while a higher loss of fat mass was observed in the HP (HP: −14.22 (10.09)%; LP: −5.26 (11.08)%; p < 0.01). Conclusions: In patients undergoing gastric sleeve surgery, the addition of a normocaloric, hyperproteic formula managed to slow down the loss of muscle mass and increase the loss of fat mass with no differences on total weight loss.