The fabled Queen of Sheba – known as “Makeda” in indigenous Ethiopian history – exists in Western history more as legend than as historical figure. It is a major task of this chapter to distinguish myth from history. Her ethnic identity of Yemeni or Sabean origin is complemented by her political identity as a ruler of Ethiopia-Abyssinia, placing her within the Red Sea littoral and thus as a woman of Afro-Asiatic importance. Why and how her historical identity became sexualized – as either one seduced or a seductress – in her famous encounter with King Solomon of Jerusalem has much to do with the patriarchal cultures in which her story has been told – in both the West and the East. This critical review of her multicultural tale will be analyzed through the cultural lenses of Western Christian, Eastern Muslim, and Ethiopian Coptic religious traditions, for her story is best related in more complex religious-political terms. In terms of “race” – a complex historical formation in its own right – the Queen of Sheba is portrayed variously depending upon the cultural tradition of the artist. Both indigenous and foreign representations will be discussed. In Ethiopian religious iconography, she is often veiled, and in folk representations, she may be portrayed as light- to brown-skinned. After the Crusades. Makeda was depicted in Western iconography as a Black woman, first in 1181 CE and continuing for centuries thereafter.