As a typical dwarf antelope, the extant Nesotragus is confined to shrub areas of open woodlands and forests in Eastern and Central Africa. Molecular phylogenetic reconstructions reveal that Nesotragus, along with Aepyceros (impala), represents the earliest crown group of Antilopinae. However, to our knowledge, fossils in relation to Nesotragus have to date not been found. Here, we report the recent discovery of a fossil dwarf antelope, Linxiatragus dengi gen. et sp. nov., from the early Late Miocene (10–9 Ma) of the Linxia Basin, adjoining the NE Tibetan Plateau. This is the first report of a fossil dwarf antelope outside of Africa and prior to Pliocene. Phylogenetic reconstructions confirm that L. dengi belongs to the clade of extant Nesotragus. Morphometric studies further suggest that the cranial morphology of Linxiatragus is intermediate between the extant Nesotragus and Gazella. A microwear study indicates that unlike extant Nesotragus, L. dengi was possibly a grazer rather than a browser, revealing that extant Nesotragus are secondarily small, an adaptation to a concealing habitat. l. dengi, as well as some other taxa (e.g., Diceros gansuensis) occurring in the NE margin of the Tibetan Plateau in the early Late Miocene, suggests a relatively arid and open regional paleoenvironmental condition, which mimicked the African Savannah woodlands ecosystem. This ecological implication is consistent with the relatively open lands in the Linxia Basin prior to the tectonic uplift of the NE Tibetan Plateau, as indicated by geological evidence. These findings might provide a new interpretation for the origin and migration of modern Sub-Saharan African Savannah mammalian assemblage through the land-bridge connecting Arabia and Asia after their hard-collision.