Criollo cattle, descendants of animals brought by Iberian colonists to the Americas, have been subject to centuries of natural and human-mediated selection in novel tropical agroecological zones. Consequently, these breeds have evolved distinct characteristics such as resistance to disease and exceptional heat tolerance. In addition to European taurine (Bos taurus) ancestry, it has been proposed that gene flow from African taurine and Asian zebu (Bos indicus) cattle has shaped the ancestry of Criollo cattle. In this study, we analysed Criollo breeds from Colombia and Venezuela using whole genome sequencing data to examine population structure and admixture at very high resolution. We did not detect evidence of African taurine admixture in Criollo cattle; however, there was evidence of longstanding zebu ancestry in one breed (Hartón del Valle). In addition, we detected selection signatures associated with a myriad of adaptive traits, revealing genes linked to thermotolerance, reproduction, fertility, immunity, and distinct coat and skin coloration traits. This study underscores the remarkable adaptability of Criollo cattle and highlights the genetic richness and potential of these breeds in the face of climate change, habitat flux, and disease challenges. Further research is warranted to leverage these findings for more effective and sustainable cattle breeding programmes.