The idea that homosexuality is ‘un-African’ is widely regarded, at least among Western scholars, as a myth concocted during the colonial era. The evidence adduced to support this consensus is largely convincing, but it does not account for all the features of contemporary African leaders’ homophobic discourses. In particular, it does not account for differences between Christian and Muslim rhetorics with respect to a putative ‘African sexuality’. Historical, ethnographic, and literary evidence suggests these differences can be traced in part to the trans-Saharan slave trade, which gave rise to racialized sexual tropes of blacks and Arabs that circulated and continue to circulate on both sides of the Sahara. In Nigeria and perhaps elsewhere, it seems that sexual stereotypes of Arabs and black Africans derived from both the trans-Saharan trade and European colonial rule have been respectively, if unevenly, mapped onto Muslims and Christians, in a way that hinders national integration. This is so even when the leaders of both groups seem to be in agreement, as when they join forces to condemn homosexuality. To ignore such religious, racial, and sexual contradictions is to ignore some of the major cultural faultlines within contemporary African nation-states and the continent overall.