The East African Shorthorn Zebu (EASZ) cattle are ancient hybrid between Asian zebu × African taurine cattle preferred by local farmers due to their adaptability to the African environment. The genetic controls of these adaptabilities are not clearly understood yet. Here, we genotyped 92 EASZ samples from Kenya (KEASZ) with more than 770,000 SNPs and sequenced the genome of a pool of 10 KEASZ. We observe an even admixed autosomal zebu × taurine genomic structure in the population. A total of 101 and 165 candidate regions of positive selection, based on genome-wide SNP analyses (meta-SS, Rsb, iHS, and ΔAF) and pooled heterozygosity (Hp) full genome sequence analysis, are identified, in which 35 regions are shared between them. A total of 142 functional variants, one novel, have been detected within these regions, in which 30 and 26 were classified as of zebu and African taurine origins, respectively. High density genome-wide SNP analysis of zebu × taurine admixed cattle populations from Uganda and Nigeria show that 25 of these regions are shared between KEASZ and Uganda cattle, and seven regions are shared across the KEASZ, Uganda, and Nigeria cattle. The identification of common candidate regions allows us to fine map 18 regions. These regions intersect with genes and QTL associated with reproduction and environmental stress (e.g., immunity and heat stress) suggesting that the genome of the zebu × taurine admixed cattle has been uniquely selected to maximize hybrid fitness both in terms of reproduction and survivability.