The history of domestic sheep (Ovis aries) in Africa remains largely unknown. After being first introduced from the Near East, sheep gradually spread through the African continent with pastoral societies. The eastern part of Africa was important either for the first diffusion of sheep southward or for putative secondary introductions from the Arabian Peninsula or southern Asia. We analysed mitochondrial DNA control region sequences of 91 domestic sheep from Kenya and found a high diversity of matrilines from the widespread haplogroup B, whereas only a single individual from haplogroup A was detected. Our phylogeography analyses of more than 500 available mitochondrial DNA sequences also identified ancestral haplotypes that were probably first introduced in Africa and are now widely distributed. Moreover, we found no evidence of an admixture between East and West African sheep. The presence of shared haplotypes in eastern and ancient southern African sheep suggests the possible southward movement of sheep along the eastern part of Africa. Finally, we found no evidence of an extensive introduction of sheep from southern Asia into Africa via the Indian Ocean trade. The overall findings on the phylogeography of East African domestic sheep set the grounds for understanding the origin and subsequent movements of sheep in Africa. The richness of maternal lineages in Kenyan breeds is of prime importance for future conservation and breeding programmes.