During the past 3000 years, cattle on the Qinghai-Xizang Plateau have developed adaptive phenotypes under the selective pressure of hypoxia, ultraviolet (UV) radiation, and extreme cold. The genetic mechanism underlying this rapid adaptation is not yet well understood. Here, we present whole-genome resequencing data for 258 cattle from 32 cattle breeds/populations, including 89 Tibetan cattle representing eight populations distributed at altitudes ranging from 3400 m to 4300 m. Our genomic analysis revealed that Tibetan cattle exhibited a continuous phylogeographic cline from the East Asian taurine to the South Asian indicine ancestries. We found that recently selected genes in Tibetan cattle were related to body size (HMGA2 and NCAPG) and energy expenditure (DUOXA2). We identified signals of sympatric introgression from yak into Tibetan cattle at different altitudes, covering 0.64%-3.26% of their genomes, which included introgressed genes responsible for hypoxia response (EGLN1), cold adaptation (LRP11), DNA damage repair (LATS1), and UV radiation resistance (GNPAT). We observed that introgressed yak alleles were associated with noncoding variants, including those in present EGLN1. In Tibetan cattle, three yak introgressed SNPs in the EGLN1 promoter region reduced the expression of EGLN1, suggesting that these genomic variants enhance hypoxia tolerance. Taken together, our results indicated complex adaptation processes in Tibetan cattle, where recently selected genes and introgressed yak alleles jointly facilitated rapid adaptation to high-altitude environments.