Background Today, African pastoralists are found mainly in the Sahel/Savannah belt spanning 6,000 km from west to east, flanked by the Sahara to the north and tropical rainforests to the south. The most significant group among them are the Fulani who not only keep cattle breeds of possible West Eurasian ancestry, but form themselves a gene pool containing some paternally and maternally‐transmitted West Eurasian haplogroups. Materials and Methods We generated complete sequences for 33 mitogenomes belonging to haplogroups H1 and U5 (23 and 10, respectively), and genotyped 16 STRs in 65 Y chromosomes belonging to haplogroup R1b‐V88. Results We show that age estimates of the maternal lineage H1cb1, occurring almost exclusively in the Fulani, point to the time when the first cattle herders settled the Sahel/Savannah belt. Similar age estimates were obtained for paternal lineage R1b‐V88, which occurs today in the Fulani but also in other, mostly pastoral populations. Maternal clade U5b1b1b, reported earlier in the Berbers, shows a shallower age, suggesting another possibly independent input into the Sahelian pastoralist gene pool. Conclusions Despite the fact that animal domestication originated in the Near East ∼ 10 ka, and that it was from there that animals such as sheep, goats as well as cattle were introduced into Northeast Africa soon thereafter, contemporary cattle keepers in the Sahel/Savannah belt show uniparental genetic affinities that suggest the possibility of an ancient contact with an additional ancestral population of western Mediterranean ancestry.