This article discusses Arab mythology prior to the arrival of Islam.
Prior to the arrival and inital codification of Islam on the Arabian Peninsula in 622 CE (or year one of the Islamic calendar) the Kaaba of Makkah, physical centre of Islam did not hold the single symbol of "the God" as it does now. The Kaaba was instead covered in symbols representing the myriad demons, djinn, demigods and other assorted creatures which represented the profoundly polytheistic environment of pre-Islamic Arabia. We can infer from this plurality an exceptionally broad context in which mythology could flourish.
The West has been exposed to the mythology of the region -- albeit one packaged for its tastes -- in the Arabian Nights. In these tales there is an initial taste of the mythology of the pre-Islamic Arabian peninsula. Ali Baba and the Forty Thieves, Aladdin, Sinbad and the other tales in Arabian Nights are all stories containing echoes of pre-Islamic mythology.