Cattle imported from the Iberian Peninsula spread throughout America in the early years of discovery and colonization to originate Creole breeds, which adapted to a wide diversity of environments and later received influences from other origins, including zebu cattle in more recent years. We analyzed uniparental genetic markers and autosomal microsatellites in DNA samples from 114 cattle breeds distributed worldwide, including 40 Creole breeds representing the whole American continent, and samples from the Iberian Peninsula, British islands, Continental Europe, Africa and American zebu. We show that Creole breeds differ considerably from each other, and most have their own identity or group with others from neighboring regions. Results with mtDNA indicate that T1c-lineages are rare in Iberia but common in Africa and are well represented in Creoles from Brazil and Colombia, lending support to a direct African influence on Creoles. This is reinforced by the sharing of a unique Y-haplotype between cattle from Mozambique and Creoles from Argentina. Autosomal microsatellites indicate that Creoles occupy an intermediate position between African and European breeds, and some Creoles show a clear Iberian signature. Our results confirm the mixed ancestry of American Creole cattle and the role that African cattle have played in their development.