Purpose: Cancer of the uterus body is the fourth most frequent tumor in females. The standard approach is a hysterectomy. Although laparoscopy (LPS) is advantageous, to date, no complex, conclusive data have compared the complication rates between LPS and laparotomy (LT) in real clinical settings, with a long-term follow up. This study aimed to compare these two approaches in terms of perioperative, and early postoperative, and late postoperative complications, and to analyze associations between complications and patient characteristics (e.g., body mass index). Materials and Methods: The outcomes of hysterectomy were retrospectively analyzed in 812 consecutive patients with uterus body tumors. Results: The frequency of peri-operative complications was similar between LPS (3.4%) and LT (2.9%). However, in the early postoperative period, complication rates were 26.6% for LT and only 3.4% for LPS (p < 0.001). A similar trend was found in the late complication rates (51.3 vs. 24.4%, respectively; p < 0.001). Higher degrees of obesity were associated with increased complication frequencies after LT in the early postoperative period (p = 0.03). Increases in BMI were linearly related to the risk of postoperative complications (p = 0.002). This relationship was not observed after LPS for any type of complication. Interestingly, the frequencies of incisional hernia and dehiscence were highly dependent on which surgeon performed the LT (p = 0.002). Conclusions: In extremely obese patients, the first method of choice should be LPS.