The Queen of Sheba is believed to have lived in the period between 1000 and 950 BC. Several regions of Africa lay claim to being her homeland. South Arabia says that her kingdom was there, the Mashona people to the south claim that the Great Zimbabwe was her palace, and there is a recent claim that she came from Nigeria. The most commonly accepted theory, however is that Queen Sheba was the ruler of a matriarchal society in the horn of Africa in what is now Ethiopia. She was known as Makeda and her life is chronicled in the Ethiopian national saga Kebra Nagast (Glory of Kings).

The visit of the queen to King Solomon at his court in Jerusalem is written of in the Bible, the Talmud, the Koran and in many Arabic and Persian folk tales. Most accounts agree that the queen came to Solomon bearing rich gifts of gems and perfumes wanting to ask Solomon about many issues...wanting to "test him with hard questions." After exchanging gifts, the queen remained for a period of time, generally thought to be about 6 months. During this time, the queen and Solomon had sex and she became pregnant with his son. The Bible skirts around the issue, but the Kebra Nagast goes into some detail. According to the Kebra Nagast, Makeda (the queen) was fed a rich dinner of highly spiced meats on the night before she was to depart for her homeland. When she got ready to go to bed, Solomon asked her to sleep with him in his chambers. She agreed, but with the condition that Solomon not force himself upon her. Solomon made a pact with Makeda that he wouldn't do so if she promised not to take anything from the palace that night. So they retired to Solomon's chambers, she to her bed and he to his bed across the room. Solomon had a pitcher of cold fresh water placed beside Makeda's bedside, and has the spiced meats made the queen thirsty, she drank some of the water. Solomon insisted that she had broken their pact, and had sex with the queen. She left the next morning for home, and bore a son 9 months and 5 days later. She named him Ibn al-Hakim, "son of the wise man." His royal name was Menelik. Menelik became the founder of Ethiopia's Solomonic dynasty. Emperor Haile Selassie was the 225th monarch of the dynasty that traced its descent back to the union of Solomon and Sheba.

The queen's story has grown over the centuries and she appears later in Christian and Muslim folklore. In medieval Christianity she is part of the legend of the true cross. The story goes that when she visited Solomon she refused to walk on a bridge because it was made of the wood which would later be turned into the cross of Christ. Her gifts to Solomon prefigure the gifts from those other pagan royals that later visited Bethlehem. In Muslim legend she is a sun worshipper who visits the faithful Solomon. She has a deformity in her lower body which varies from having webbed feet to a donkey's hoof or just exceptionally hairy legs. Solomon heals her of these various ills (in the latter case by inventing a depilatory cream made from lime and arsenic) and she converts to the true faith. This particular story is pretty amusing, with Solomon having a glass floor built in front of his throne which he told the queen was water. As the queen raised her skirts to cross the supposed water, Solomon was able to verify that her legs were indeed quite hairy. What a guy!

The telling of the story of The Queen of Sheba has also changed with the times. During the middle ages, the queen was often portrayed as acting in open defiance of nature's equilibrium and God's design, and her tale became one of sexual politics and conniving women. During this same time frame, seldom was the queen portrayed as being black, which she most certainly was. Various tellings of her tale have also featured her submitting to Solomon because of his gender and color and giving up her right to rule. Interestingly, in the new testament of the Bible, Matthew 12:42 the Queen of Sheba (called the Queen of the South) is foretold to be sitting with Jesus on the day of judgement.