A study of two documents from the Cairo Genizah, a vast repository of medieval Jewish writings recovered from a synagogue in Fusṭāṭ, Egypt, one hundred years ago, shows the importance of this archive for the history of medieval Yemen and, in particular, for the role that Yemen played in the Indian Ocean trade as both a commercial and administrative hub. The first document is a letter from Aden to Fusṭāṭ, dated 1133CE, explaining the Aden Jewish community’s failure to raise funds to send to the heads of the Palestinian Gaonate in Egypt. It signals the decline of that venerable institution and the increasing independence of the Yemeni Jews. The second text is a legal document, produced by an Egyptian Jewish trader who intended to travel to Yemen, but who wished to ensure his wife was provided for in his absence. Both documents show the close ties between the Egyptian and Yemeni Jewish communities and the increasing commercial importance of Yemen to Egyptian traders.