We study the major levels of Y-chromosome haplogroup variation in 15 Sudanese populations by typing major Y-haplogroups in 445 unrelated males representing the three linguistic families in Sudan. Our analysis shows Sudanese populations fall into haplogroups A, B, E, F, I, J, K, and R in frequencies of 16.9, 7.9, 34.4, 3.1, 1.3, 22.5, 0.9, and 13% respectively. Haplogroups A, B, and E occur mainly in Nilo-Saharan speaking groups including Nilotics, Fur, Borgu, and Masalit; whereas haplogroups F, I, J, K, and R are more frequent among Afro-Asiatic speaking groups including Arabs, Beja, Copts, and Hausa, and Niger-Congo speakers from the Fulani ethnic group. Mantel tests reveal a strong correlation between genetic and linguistic structures (r = 0.31, P = 0.007), and a similar correlation between genetic and geographic distances (r = 0.29, P = 0.025) that appears after removing nomadic pastoralists of no known geographic locality from the analysis. The bulk of genetic diversity appears to be a consequence of recent migrations and demographic events mainly from Asia and Europe, evident in a higher migration rate for speakers of Afro-Asiatic as compared with the Nilo-Saharan family of languages, and a generally higher effective population size for the former. The data provide insights not only into the history of the Nile Valley, but also in part to the history of Africa and the area of the Sahel.