Background Human population history in the Holocene was profoundly impacted by changes in lifestyle following the invention and adoption of food-production practices. These changes triggered significant increases in population sizes and expansions over large distances. Here we investigate the population history of the Fulani, a pastoral population extending throughout the African Sahel/Savannah belt. Results Based on genome-wide analyses we propose that ancestors of the Fulani population experienced admixture between a West African group and a group carrying both European and North African ancestries. This admixture was likely coupled with newly adopted herding practices, as it resulted in signatures of genetic adaptation in contemporary Fulani genomes, including the control element of the LCT gene enabling carriers to digest lactose throughout their lives. The lactase persistence (LP) trait in the Fulani is conferred by the presence of the allele T-13910, which is also present at high frequencies in Europe. We establish that the T-13910 LP allele in Fulani individuals analysed in this study lies on a European haplotype background thus excluding parallel convergent evolution. We furthermore directly link the T-13910 haplotype with the Lactase Persistence phenotype through a Genome Wide Association study (GWAS) and identify another genomic region in the vicinity of the SPRY2 gene associated with glycaemic measurements after lactose intake. Conclusions Our findings suggest that Eurasian admixture and the European LP allele was introduced into the Fulani through contact with a North African population/s. We furthermore confirm the link between the lactose digestion phenotype in the Fulani to the MCM6/LCT locus by reporting the first GWAS of the lactase persistence trait. We also explored other signals of recent adaptation in the Fulani and identified additional candidates for selection to adapt to herding life-styles.