Background: Recently, it was reported that minimally invasive surgery (MIS) has a negative impact on early-stage cervical cancer (ECC) patient survival. At the same time, advantages of MIS regarding quality of life and low rate of intra- and postoperative complications are well known. Therefore, it is essential to select patients who may benefit from MIS without worsening their oncologic outcomes. The aim of this study is to investigate which pathological factors could guide surgeons’ choice about the best approach in ECC. Patients and Methods: Patients with 2009 FIGO stage from IA1 with lymphovascular space invasion (LVSI) to IB1/IIA1 treated by open or laparoscopic surgery were judged eligible for the study. Disease-free survivals (DFS) of both approaches were tested in subgroups, defined according to histology, tumor size, grading, LVSI, parametrial involvement, and nodal status. Results: A total of 423 patients were enrolled (217 in the open and 206 in the laparoscopic group). No difference between open surgery and laparoscopy was found among subgroups defined according to histology, grading, LVSI, parametrial involvement, or nodal status. Among patients with tumor > 20 mm, laparoscopy showed a significantly higher relapse risk [hazard ratio (HR): 2.103, p = 0.030]. Among patients with tumor < 20 mm, laparoscopy showed DFS superimposable to open surgery (HR: 0.560, p = 0.128). Conclusions: Tumor size of 20 mm appeared as the only independent discrimination criterion in patients whose prognosis is affected by surgical approaches.