The evolutionary history of Rhinocerotidae has been the subject of significant debate among palaeontologists, with several paradigm shifts within the last quarter century, typically centered around a speculated deep-basal split between Rhinocerotinae and Elasmotheriinae. Here, we recover an endogenous ancient enamel proteome from an Early Miocene (20+Ma) old rhinocerotid from the Haughton Formation of Canada’s High Arctic. Ancient proteomes sufficient for phylogenetic analysis have not previously been recovered from beyond the Pliocene, making it difficult to reconstruct the evolutionary relationships and divergence times of fossil taxa that are beyond the reach of ancient DNA. Here, phylogenetic analysis of our proteomic data suggests the split between Elasmotheriinae and Rhinocerotinae occurred much later than previously speculated, in the late Eocene or Oligocene. The authenticity of ancient the ancient proteome is supported by a suite of post-translational modifications associated with advanced degradation, including a significant degree of arginine->ornithine conversion and high rates of advanced forms of tryptophan and histidine oxidation.