Although the Koran encourages overcoming genealogical relationship patters, medieval Arabic texts continued to be characterized by the language of tribe and kinship. The most important central themes of this genealogical narrative, which often seem related, were 1. the Arabic tribal system; 2. its relation to biblical genealogies and to the positioning of the prophets within this genealogical net; 3. the so-called “Meccan Legends” surrounding the rise of the Quraysh as a hegemonic group; 4. myths of wandering. This article uses a telling example to illustrate how, in a complex genealogical narrative that deals with each of these themes, a tightly woven network of associations and ties between groups and individuals was produced that served to valorize and glorify Arab ethnicity, Arabia as a space of divine activity and the prophet Muḥammad. The subject is the legend of the Babylonian king Nebuchadnezzar’s expulsion of Maʿadd, the eponym of the Northern Arabs and ancestor of the prophet, and of Maʿadd’s eventual immigration to Mecca.