Updated publication reference for PubMed record(s): 31511700. Ancient DNA (aDNA) sequencing has enabled reconstruction of speciation, migration, and admixture events for extinct taxa. Outside the permafrost, however, irreversible aDNA post-mortem degradation has so far limited aDNA recovery to the past ~0.5 million years (Ma). Contrarily, multiple analyses suggested the presence of protein residues in Cretaceous fossil remains. Similarly, tandem mass spectrometry (MS) allowed sequencing ~1.5 million year (Ma) old collagen type I (COL1), though with limited phylogenetic use. In the absence of molecular evidence, the speciation of several Early and Middle Pleistocene extinct species remain contentious. In this study, we address the phylogenetic relationships of the Eurasian Pleistocene Rhinocerotidae using a ~1.77 Ma old dental enamel proteome of a Stephanorhinus specimen from the Dmanisi archaeological site in Georgia (South Caucasus). Molecular phylogenetic analyses place the Dmanisi Stephanorhinus as a sister group to the woolly (Coelodonta antiquitatis) and Merck’s rhinoceros (S. kirchbergensis) clade. We show that Coelodonta evolved from an early Stephanorhinus lineage and that the latter includes at least two distinct evolutionary lines. As such, the genus Stephanorhinus is currently paraphyletic and requires systematic revision. We demonstrate that Early Pleistocene dental enamel proteome sequencing overcomes the limits of ancient collagen- and aDNA-based phylogenetic inference. It also provides additional information about the sex and taxonomic assignment of the specimens analysed. Dental enamel, the hardest tissue in vertebrates, is highly abundant in the fossil record. Our findings reveal that palaeoproteomic investigation of this material can push biomolecular investigation further back into the Early Pleistocene.