The Fulani people, one of the most important pastoralist groups in sub-Saharan Africa, are still largely underrepresented in population genomic research. They speak a Niger-Congo language called Fulfulde or Pulaar and live in scattered locations across the Sahel/Savannah belt, from the Atlantic Ocean to Lake Chad. According to historical records, their ancestors spread from Futa Toro in the Middle Senegal Valley to Futa-Jallon in Guinea and then eastward into the Sahel belt over the past 1,500 years. However, the earlier history of this traditionally pastoral population has not been well studied. To uncover the genetic structure and ancestry of this widespread population, we gathered genome-wide genotype data from 460 individuals across 18 local Fulani populations, along with comparative data from both modern and ancient worldwide populations. This represents a comprehensive geographically wide-scaled genome-wide study of the Fulani. We revealed a genetic component closely associated with all local Fulani populations, suggesting a shared ancestral component possibly linked to the beginning of African pastoralism in the Green Sahara. Comparison to ancient DNA results also identified the presence of an ancient Iberomaurusian-associated component across all Fulani groups, providing additional insights into their deep genetic history. Additionally, our genetic data indicate a later Fulani expansion from the western to the eastern Sahel, characterized by a clinal pattern and admixture with several other African populations north of the equator.