Historia e hershme e Mekës nuk është e dokumentuar mirë, ^[7] me referencën e parë joislame që u shfaq në vitin 741 të erës sonë, pas vdekjessë Profetit Muhamed , në Kronikën Bizantine-Arabe.Ky burim gabimisht e vendos Mekën në Mesopotami në vend të rajonit të Hejazit në Arabinë perëndimore, ku burimet arkeologjike dhe tekstuale janë të pakta.^[8]Medina, nga ana tjetër, ka qenë e banuar të paktën që nga shekulli i 9-të para Krishtit.^[9] Në shekullin e IV të erës sonë, ajo ishte shtëpia e fiseve arabe nga Jemeni dhe tre fiseve çifute: Benu Kaynuqa, Benu Kurejza dhe Benu Nadir.^[10]Muhamedi , Profeti i Islamit, lindi në Mekë rreth vitit 570 të erës sonë dhe filloi shërbimin e tij atje në vitin 610 të erës sonë.Ai migroi në Medine në vitin 622 të erës sonë, ku bashkoi fiset arabe nën Islamin.Pas vdekjes së tij në vitin 632 të erës sonë, Ebu Bekri u bë halifi i parë, i pasuar nga Omari, Uthman ibn al-Affani dhe Ali ibn Ebi Talibi.Kjo periudhë shënoi formimin e Kalifatit Rashidun .Nën Rashidun dhe Kalifatin Umajad pasues, muslimanët e zgjeruan territorin e tyre në mënyrë të konsiderueshme, nga Gadishulli Iberik në Indi.Ata mposhtën ushtrinë bizantine dhe përmbysën Perandorinë Persiane , duke e zhvendosur fokusin politik të botës myslimane në këto territore të fituara rishtazi.Pavarësisht këtyre zgjerimeve, Meka dhe Medina mbetën qendrore për spiritualitetin islam.Kurani urdhëron pelegrinazhin e Haxhit në Mekë për të gjithë muslimanët e aftë.Mesxhid al-Haram në Mekë, me Qaben, dhe Mesxhid al-Nabawi në Medine, që përmban varrin e Muhamedit, kanë qenë vende kryesore pelegrinazhi që nga shekulli i VII.^[11]Pas rënies së Perandorisë Umajad në vitin 750 të erës sonë, rajoni që do të bëhej Arabia Saudite iu kthye kryesisht qeverisjes tradicionale fisnore, e cila vazhdoi pas pushtimeve fillestare myslimane.Kjo zonë karakterizohej nga një peizazh i luhatshëm i fiseve, emirateve fisnore dhe konfederatave, shpesh të cilave u mungonte stabiliteti afatgjatë.^[12]Muavije I, kalifi i parë umajad dhe me origjinë nga Meka, investoi në vendlindjen e tij duke ndërtuar ndërtesa dhe puse.^[13] Gjatë periudhës Marvanid, Meka evoluoi në një qendër kulturore për poetë dhe muzikantë.Pavarësisht kësaj, Medina kishte një rëndësi më të madhe për një pjesë të konsiderueshme të epokës Umajad, pasi ishte vendbanimi i aristokracisë myslimane në lulëzim.^[13]Gjatë mbretërimit të Jezidit I pashë trazira të konsiderueshme.Revolta e Abd Allah bin al-Zubair çoi në hyrjen e trupave siriane në Mekë.Kjo periudhë dëshmoi një zjarr katastrofik që dëmtoi Qaben, të cilën Ibn al-Zubair e rindërtoi më pas.^[13] Në 747, një rebel Kharixhit nga Jemeni pushtoi për pak kohë Mekën pa rezistencë, por shpejt u rrëzua nga Marvan II.^[13] Më në fund, në vitin 750, kontrolli i Mekës dhe kalifati më i madh kaloi te Abasidët.^[13]