The settlement of the Tibetan Plateau epitomizes human adaptation to a high-altitude environment that poses great challenges to human activity. Here, we reconstruct a 4,000-year maternal genetic history of Tibetans using 128 ancient mitochondrial genome data from 37 sites in Tibet. The phylogeny of haplotypes M9a1a, M9a1b, D4g2, G2a'c, and D4i show that ancient Tibetans shared the most recent common ancestor (TMRCA) with ancient Middle and Upper Yellow River populations around the Early and Middle Holocene. In addition, the connections between Tibetans and Northeastern Asians varied over the past 4,000 years, with a stronger matrilineal connection between the two during 4,000-3,000 BP, and a weakened connection after 3,000 BP, that were coincident with climate change, followed by a reinforced connection after the Tubo period (1,400-1,100 BP). Besides, an over 4,000-year matrilineal continuity was observed in some of the maternal lineages. We also found the maternal genetic structure of ancient Tibetans was correlated to the geography and interactions between ancient Tibetans and ancient Nepal and Pakistan populations. Overall, the maternal genetic history of Tibetans can be characterized as a long-term matrilineal continuity with frequent internal and external population interactions that were dynamically shaped by geography, climate changes, as well as historical events.