The Black Stone of the Kabaa (al-Hajar al-Aswad) has been an object of veneration in Mecca since the 5th century by the Banu Quraysh (literally Tribe Quraysh) –the tribe of Mohammed. According to some historic accounts the Banu Quraysh were an amalgamation of families of differing tribes which gathered under the leadership of Qusayy bin Kilab to begin the expedition to form a new settlement which was to become Mecca. The Banu Quraysh claim to be a branch of the Banu Kinanah was due to the Qusayy bin Kilab being a member of the tribe. The Quraysh migrated from what is today Mudiyah in Yemen when the area, at the time, had experienced some flooding.
The Banu Quraysh were a polytheist people who venerated a pantheon deities (according to some Mohammedan accounts about 300). The religion of the Quraysh were very syncretic in nature with deities borrowed from other tribes in the region Nabataeans , Syrians, Mesopotamians, Persians and anyone else they dealt with. According to local accounts, a Kaaba had existed in Mudiyah, but in which form is lost in history for the Arabs as a whole were not a literate people in general and left very little in the way of a written history – though a strong oral historic tradition existed at the time. This oral tradition exists from accounts written by Persian, Mesopotamians and Syrians about the region in passing. When the Banu Quraysh established the town of Mecca in the 5th century, they built a Kaaba to house their pantheon of gods in their new city as well. Various Kaaba have existed in and around the area Southern Arabia, including, at the time in the cities of Najran and Sindad.
Several historic accounts, including Hisham ibn al-Kalbi, exist which provide an insight to the religions adhered to by existent Arab tribes of the day. The principle among these deities was al-Lah (synonymous with Hubal), the moon god of the Banu Quraysh and considered the greatest of the gods. Now, al-Lah had the primordial wife (al-Lat) and two principle daughters – al-Ussa and al-Manat which the Koran speaks of directly (this are now called the Satanic Verses for which Salman Rushdi received the death penalty for his elaboration). Al-Lah took to himself these daughters who are the “wandering stars of the heavens” aka planets in our common vernacular, as his wives and the progeny of which are the stars of the heavens. Al-Ussa was the patron goddess of the Banu Quraysh and acted in the role of the goddess of fertility.