Although classified as an African taurine breed, the genomes of Sheko cattle are an admixture of Asian zebu and African taurine ancestries. They populate the humid Bench Maji zone in Sheko and Bench districts in the south-western part of Ethiopia and are considered as a trypanotolerant breed with high potential for dairy production. Here, we investigate the genome of Sheko cattle for candidate signatures of adaptive introgression and positive selection using medium density genome-wide SNP data. Following locus-ancestry deviation analysis, 15 and 72 genome regions show substantial excess and deficiency in Asian zebu ancestry, respectively. Nine and 23 regions show candidate signatures of positive selection following extended haplotype homozygosity (EHH)-based analyses (iHS and Rsb), respectively. The results support natural selection before admixture for one iHS, one Rsb and three zebu ancestry-deficient regions. Genes and/or QTL associated with bovine immunity, fertility, heat tolerance, trypanotolerance and lactation are present within candidate selected regions. The identification of candidate regions under selection in Sheko cattle warrants further investigation of a larger sample size using full genome sequence data to better characterise the underlying haplotypes. The results can then support informative genomic breeding programmes to sustainably enhance livestock productivity in East African trypanosomosis infested areas.