Tibetan sheep are the most common and widespread domesticated animals on the Qinghai-Tibetan Plateau (QTP) and have played an essential role in the permanent human occupation of this high-altitude region. However, the precise timing, route, and process of sheep pastoralism in the QTP region remain poorly established, and little is known about the underlying genomic changes that occurred during the process. Here, we investigate the genomic variation in Tibetan sheep using whole-genome sequences, single nucleotide polymorphism arrays, mitochondrial DNA, and Y-chromosomal variants in 986 samples throughout their distribution range. We detect strong signatures of selection in genes involved in the hypoxia and ultraviolet signaling pathways (e.g., HIF-1 pathway and HBB and MITF genes) and in genes associated with morphological traits such as horn size and shape (e.g., RXFP2). We identify clear signals of argali (Ovis ammon) introgression into sympatric Tibetan sheep, covering 5.23-5.79% of their genomes. The introgressed genomic regions are enriched in genes related to oxygen transportation system, sensory perception, and morphological phenotypes, in particular the genes HBB and RXFP2 with strong signs of adaptive introgression. The spatial distribution of genomic diversity and demographic reconstruction of the history of Tibetan sheep show a stepwise pattern of colonization with their initial spread onto the QTP from its northeastern part ∼3,100 years ago, followed by further southwest expansion to the central QTP ∼1,300 years ago. Together with archeological evidence, the date and route reveal the history of human expansions on the QTP by the Tang-Bo Ancient Road during the late Holocene. Our findings contribute to a depth understanding of early pastoralism and the local adaptation of Tibetan sheep as well as the late-Holocene human occupation of the QTP.