Mandibular and dental material of hyaenids from the Central Asian localities of Zasukhino-3 (Russia) and Nalaikha (Mongolia), dating to the late Early Pleistocene (0.9–0.78 Ma) was identified as giant hyena Pachycrocuta brevirostris based on morphological and size similarities. Comparative analysis of Eurasian P. brevirostris from different stratigraphic levels (from 2.1 to 0.5 Ma) revealed two evolutionary stages of the lower cheek teeth of the giant hyenas. The stages are determined as morphotypes A and B, directed toward the differentiation of the function of premolar and enhancing the cutting function of m1. We traced the microprocesses that occurred during the transition from the primitive structure of the m1 talonid to its more advanced state. This event occurred during the transition from the late Villafranchian to the Epivillafranchian (ca. 1.1–0.9 Ma). The stabilized advanced morphotype B was found in samples from Zasukhino-3, Nalaikha, and other close-in-age localities such as Lakhuti-2. The new finds from Asian Russia and Mongolia suggest that P. brevirostris from these regions represent a single giant hyena population occupying the northernmost part of their Asian range.