Turano-Mongolian cattle are a group of taurine cattle from Northern and Eastern Asia with distinct morphological traits, which are known for their ability to tolerate harsh environments, such as the Asian steppe and the Tibetan plateau. Through the analysis of 170 mitogenomes from ten modern breeds, two sub-lineages within T3 (T3119 and T3055) were identified as specific of Turano-Mongolian cattle. These two T3 sub-lineages, together with the previously identified T4, were also present in six Neolithic samples, dated to ~3900 years BP, which might represent the earliest domestic taurine stocks from Southwest Asia. The rare haplogroup Q, found in three Tibetan cattle, testifies for the legacy of ancient migrations from Southwest Asia and suggests that the isolated Tibetan Plateau preserved unique prehistoric genetic resources. These findings confirm the geographic substructure of Turano-Mongolian cattle breeds, which have been shaped by ancient migrations and geographic barriers.