Purpose This study aimed to evaluate body composition changes and the determinants of fat-free mass loss (FFML) up to 3 years after sleeve gastrectomy (SG) and one-anastomosis gastric bypass (OAGB). Materials and Methods A prospective study was conducted on 3864 patients with severe obesity who underwent either SG (2746, 76.1% women, mean age: 39.2 +/- 11.6 years, and BMI: 44.3 +/- 5.6 kg/m(2)) or OAGB (1118, 82.2% women, age: 39.9 +/- 10.7 years, BMI: 45.6 +/- 6.3 kg/m(2)). Body composition parameters were measured by bioelectrical impedance analysis preoperatively and 1, 3, 6, 9, 12, 18, 24, and 36 months after surgery. Changes in body composition were assessed using the propensity matched generalized estimated equation (GEE) method. The determinants of fat-free mass loss/weight loss (FFML/WL%) were defined using a mixed-model GEE analysis. Results Means of FM, FFM, and FFML/WL% decreased significantly in both study groups (P-trend < 0.001). Changes in BMI, EWL%, FM, and FFML/WL% were different between the two groups (P-between < 0.05). The results showed a better FFM preservation and a greater FM loss over time in the OAGB group compared to the SG group (P-interaction < 0.05). FFML during the first 3 months was greater in the SG compared to the OAGB group (P < 0.001). SG surgery, higher preoperative BMI, and female gender were associated with greater FFML/WL%. Conclusion In the SG compared to the OAGB group, FFML was greater, especially early after the surgery, emphasizing the need for therapeutic interventions such as regular exercise programs and dietary intake modifications.