The Y chromosome is a valuable genetic marker for studying the origin and influence of paternal lineages in populations. In this study, we conducted Y-chromosomal lineage-tracing in Arabian horses. First, we resolved a Y haplotype phylogeny based on the next generation sequencing data of 157 males from several breeds. Y-chromosomal haplotypes specific for Arabian horses were inferred by genotyping a collection of 145 males representing most Arabian sire lines that are active around the globe. These lines formed three discrete haplogroups, and the same haplogroups were detected in Arabian populations native to the Middle East. The Arabian haplotypes were clearly distinct from the ones detected in Akhal Tekes, Turkoman horses, and the progeny of two Thoroughbred foundation sires. However, a haplotype introduced into the English Thoroughbred by the stallion Byerley Turk (1680), was shared among Arabians, Turkomans, and Akhal Tekes, which opens a discussion about the historic connections between Oriental horse types. Furthermore, we genetically traced Arabian sire line breeding in the Western World over the past 200 years. This confirmed a strong selection for relatively few male lineages and uncovered incongruences to written pedigree records. Overall, we demonstrate how fine-scaled Y-analysis contributes to a better understanding of the historical development of horse breeds.