Archaeological and epigraphic traces of ancient South-Arabian trade with the Middle East go back to the early 8th century B.C. One of the caravan routes, going eventually through the oasis of Taima, reached Tell el-Kheleifeh, at the outskirts of present-day Aqaba, and continued northwards, also to Jerusalem and to Samaria, or to the north-west, through Khirbet 'Ar'ara (Aroer) and Tell as-Seba (Tel Beersheva) to Gaza and Egypt. South-Arabian inscriptions from the 7th century B.C. found at Jerusalem, as well as the knowledge of the role played by Arabian queens in the Assyrian period, may explain the origins of the story-tale of I Kings 10, 1-13 reporting the visit of a nameless queen of Sheba to Jerusalem. She got different names in later traditions, but not the one of Gahimat, the first known queen of Sheba at the end of the 8th century B.C., whose inscription from the Al-'Aql gorge is briefly commented upon in the article. Besides, a stamp found at Beitin reveals the presence of traders from Hadhramaut and a religious centre was established very likely by men from Taima at Arad, at the southern edge of the Judaean Highland, in an area where North-Arabian names seem to appear as well, also in the Book Genesis 23.