The sequencing of ancient DNA has enabled the reconstruction of speciation, migration and admixture events for extinct taxa(1). However, the irreversible post-mortem degradation(2) of ancient DNA has so far limited its recovery-outside permafrost areasto specimens that are not older than approximately 0.5 million years (Myr)(3). By contrast, tandem mass spectrometry has enabled the sequencing of approximately 1.5-Myr-old collagen type I-4. and suggested the presence of protein residues in fossils of the Cretaceous period(5)-although with limited phylogenetic use(6). In the absence of molecular evidence, the speciation of several extinct species of the Early and Middle Pleistocene epoch remains contentious. Here we address the phylogenetic relationships of the Eurasian Rhinocerotidae of the Pleistocene epoch(7-9), using the proteome of dental enamel from a Stephanorhinus tooth that is approximately 1.77-Myr old, recovered from the archaeological site of Dmanisi (South Caucasus, Georgia)(10). Molecular phylogenetic analyses place this Stephanorhinus as a sister group to the Glade formed by the woolly rhinoceros (Coelodonta antiquitatis) and Merck's rhinoceros (Stephanorhinus kirchbergensis). We show that Coelodonta evolved from an early Stephanorhinus lineage, and that this latter genus includes at least two distinct evolutionary lines. The genus Stephanorhinus is therefore currently paraphyletic, and its systematic revision is needed. We demonstrate that sequencing the proteome of Early Pleistocene dental enamel overcomes the limitations of phylogenetic inference based on ancient collagen or DNA. Our approach also provides additional information about the sex and taxonomic assignment of other specimens from Dmanisi. Our findings reveal that proteomic investigation of ancient dental enamel-which is the hardest tissue in vertebrates(11), and is highly abundant in the fossil record-can push the reconstruction of molecular evolution further back into the Early Pleistocene epoch, beyond the currently known limits of ancient DNA preservation.