This paper investigates the question of legitimacy in al-Andalus by looking at the moment in which the encyclopedic adab anthology of al-‘Iqd, and the Umayyad caliphate of ‘Abd al-Rahman III simultaneously emerged. The politics through which both projects, separately and in relation to one another, inhabit genealogies of eastern traditions constitutes the main area of inquiry. The analysis traces the trajectories of cultural elements as they travelled to al-Andalus from eastern centers, to complicate notions of reuse, borrowing and restoration that plot and confirm claims of Arabo-Islamic cultural continuity. Recognizing forms of borrowing as dynamic processes, I show how in the coincidence of the two ventures, a uniquely Andalusi conception of legitimacy can be located and identified. In assuming an encyclopedic character, I argue, al-'Iqd as an adab anthology ushered new forms of readership that became central in negotiating aspects of Umayyad political power. I further show how through innovating a progressive theory of knowledge that seemingly adheres to broader cultural consensus, al-‘Iqd succeeded in shaping the Umayyad caliphate of al-Andalus. Through engaging with debates of origins, genealogies and reproduction, the paper hopes to present new opportunities for apprehending legitimacy as a realm of contestation and negotiation.