The fossil record of cheetahs in eastern Asia is notably scarce and predominantly fragmented, leaving the evolution of this lineage in eastern Asia largely enigmatic. In this study, we present new findings from two early Middle Pleistocene sites, the upper deposits (L2) of Jinyuan Cave (Dalian) and Zhoukoudian Loc.13 (Beijing). These specimens are identified here as Acinonyx pleistocaenicus and represent the latest and largest-sized member of the species. Acinonyx pleistocaenicus shows a suit of craniodental traits that distinguishes it from the earlier Early Pleistocene A. pardinensis, and relates it to modern A. jubatus, and should be regarded as a valid species. Shortly after the age represented by Zhoukoudian Loc. 13 (0.6–0.7 Ma), the giant cheetah was replaced by much smaller and morphologically different Acinonyx intermedius. This transition supports the independence of these two species, and the latter was likely a new immigrant from Africa around the Early-Middle Pleistocene boundary, together with Panthera spelaea, Panthera pardus, and Parahyaena prisca.