In this study, we show how Y-specific interspersed multilocus microsatellites, which are loci that yield several amplified bands differing in size from the same male individual and PCR reaction, are a powerful source of information for tracing the history of cattle. Our results confirm the existence of three main groups of sires, which are separated by evolutionary time and clearly predate domestication. These three groups are consistent with the haplogroups previously identified by Götherström et al. (2005) using five Y-specific segregating sites: Y1 and Y2 in taurine (Bos taurus) cattle and Y3 in zebu (Bos indicus) cattle. The zebu cattle cluster clearly originates from a domestication process that was geographically and temporally separated from that of taurine clusters. Our analyses further suggest that: (i) introgression of wild sire genetic material into domesticated herds may have a significant role in the formation of modern cattle, including the formation of the Y1 haplogroup; (ii) a putative domestication event in Africa probably included local Y2-like wild sires; (iii) the West African zebu cattle Y-chromosome may have partially originated from an ancient introgression of humped cattle into Africa; and (iv) the high genetic similarity among Asian zebu sires is consistent with a single domestication process.