The Nile River valley has a long history of human habitation, with finds of the earliest anatomically modern humans close by and housing some of the earliest civilizations, but it has not yet been extensively explored using genome-wide population-genetic data. Due to its geographic location, history and linguistic diversity, Sudan and South Sudan cover interesting areas to investigate human demographic history. Previous studies in the area have focused on uniparentally inherited markers, microsatellites or small SNP-marker panels. We investigate 18 Sudanese and South Sudanese populations by genotyping 221 individuals for approximately 5 million SNPs using the Illumina platform. We compare this novel dataset to available SNP data of surrounding geographic regions, as well as the 1000 Genomes and HGDP datasets. This dense marker set allows us to address questions relating to the demographic history of various populations from the area and reveals detailed population structure correlating with geography and language. By using a series of summary statistics, we infer further details about the populations’ demographic history. A decrease in heterozygosity in migrant populations of the Sudan, such as the Hausa, indicates a small population size. We combine genetic, geographic and linguistic information to paint a detailed picture of the Northeast African population history.