My paper explores the travel narratives of medieval Arab travelers Ibn Battuta and Ibn Khaldun, who used their representations of Black Africa and Africans to validate their Arab national identity vis-?-vis the world around them. My paper thus contributes to the study of race and its history through literature, showing the unique ways race has manifested itself in the Arab world. In Morocco, the coming of Islam in the seventh century and the introduction of a writing culture in Arabic language encouraged not only the flourishing of a literary tradition, but also a trans-Saharan slave trade. At the time when Ibn Battuta and Ibn Khaldun emerged as new literary talents, Black slaves were the dominant export to North Africa. The travel accounts of these two North African writers coincided with the Moroccan Empire, which controlled trade between Morocco and Timbuktu for over 300 years. Racial stereotypes that denigrated blacks and justified slavery were prevalent among people at the time, and might have affected these writers' perspectives on Black Africans. While Ibn Battuta's ingrained Muslim identity in Rihla Ibn Battuta demanded an adherence to the dominance of the Muslim 'Umma,' and the complete rejection of non-Muslims, Ibn Khaldun's disparaging remarks about the blackness of Africans in his Kitab Al-Ibar/Muqaddima offer an important insight into the racial construction of Black Africans that will influence many writers after his time. This paper also investigates how such travel narratives from the Middle-Ages contributed to deprecatory cultural attitudes toward Africa and Africans, and to what extent they have affected later domineering attitudes towards Africans. My theoretical framework draws upon Arabs' conceptualizations of race that I derive from the literary texts, as well as key concepts of modern critical race theory. In my application of critical race theory to the Arabic context, I direct greater attention to the contrast between early Arab theories which promote a biological view of race, and the theories of modern critical race theorists who view race as a sociocultural concept. I also discuss the limitations of critical race theory when we approach Arabic literature with critical tools devised in modern and postmodern contexts.