A novel histopathological grading system based on tumour budding and cell nest size has recently been shown to outperform conventional (WHO-based) grading algorithms in several tumour entities such as lung, oral, and oesophageal squamous cell carcinoma (SCC) in terms of prognostic patient stratification. Here, we tested the prognostic value of this innovative grading approach in two completely independent cohorts of SCC of the uterine cervix. To improve morphology-based grading, we investigated tumour budding activity and cell nest size as well as several other histomorphological factors (e.g., keratinization, nuclear size, mitotic activity) in a test cohort (n = 125) and an independent validation cohort (n = 122) of cervical SCC. All parameters were correlated with clinicopathological factors and patient outcome. Small cell nest size and high tumour budding activity were strongly associated with a dismal patient prognosis (p < 0.001 for overall survival [OS], disease-specific survival, and disease-free survival; test cohort) in both cohorts of cervical SCC. A novel grading algorithm combining these two parameters proved to be a highly effective, stage-independent prognosticator in both cohorts (OS: p < 0.001, test cohort; p = 0.001, validation cohort). In the test cohort, multivariate statistical analysis of the novel grade revealed that the hazard ratio (HR) for OS was 2.3 for G2 and 5.1 for G3 tumours compared to G1 neoplasms (p = 0.010). In the validation cohort, HR for OS was 3.0 for G2 and 7.2 for G3 tumours (p = 0.012). In conclusion, our novel grading algorithm incorporating cell nest size and tumour budding allows strongly prognostic histopathological grading of cervical SCC superior to WHO-based grading. Therefore, our data can be regarded as a cross-organ validation of previous results demonstrated for oesophageal, lung, and oral SCC. We suggest this grading algorithm as an additional morphology-based parameter for the routine diagnostic assessment of this tumour entity.