In recent years, the evolutionary history of rhinoceroses has been extensively developed and clarified, notably with the help of morpho-anatomical and molecular-based phylogenetic analyses. Within Rhinocerotidae, the genus Coelodonta Bronn, 1831, is one of the most representative icons of the Ice Ages, ranging from the Late Pliocene to the latest Pleistocene. Nevertheless, few studies have focused on its phylogeny and the systematic assignment of its Middle Pleistocene representatives is fervently debated. Indeed, the earliest European specimens of Coelodonta are considered as documenting either C. tologoijensis Belyaeva in Vangengejm, 1966, of Russian affinities, or an early subspecies of Coelodonta antiquitatis (Blumenbach, 1799), C. a. praecursor Guérin, 1980. Accordingly, C. antiquitatis would then first occur in the Late Pleistocene or in the Middle Pleistocene depending on the hypothesis. The current work aims to describe and identify cranio-mandibular and postcranial remains of Coelodonta from the Middle Pleistocene Les Rameaux locality, SW France, and to compare them with all Eurasian representatives of the genus, including the oldest European specimens from Bad Frankenhausen. A combination of morphometric and morpho-anatomical phylogenetic analyses strongly supports C. a. praecursor and C. a. antiquitatis as distinct and valid subspecies and allows for the refutation of the taxonomic assignment of the Bad Frankenhausen skull to C. tologoijensis. This work proposes the first comprehensive phylogeny for Coelodonta, further tracing its biogeographical history.