Species of the Bos genus, including taurine cattle, zebu, gayal, gaur, banteng, yak, wisent and bison, have been domesticated atleast four times and have been an important source of meat, milk and power for many human cultures. We sequence the genomesof gayal, gaur, banteng, wisent and bison, and provide population genomic sequencing of an additional 98 individuals. We usethese data to determine the phylogeny and evolutionary history of these species and show that the threatened gayal is an inde-pendent species or subspecies. We show that there has been pronounced introgression among different members of this genus,and that it in many cases has involved genes of considerable adaptive importance. For example, genes under domesticationselection in cattle (for example, MITF) were introgressed from domestic cattle to yak. Also, genes in the response-to-hypoxiapathway (for example, EGLN1, EGLN2 and HIF3a) have been introgressed from yak to Tibetan cattle, probably facilitating theiradaptation to high altitude. We also validate that there is an association between the introgressed EGLN1 allele and haemoglo-bin and red blood cell concentration. Our results illustrate the importance of introgression as a source of adaptive variation andduring domestication, and suggest that the Bos genus evolves as a complex of genetically interconnected species with sharedevolutionary trajectories.