Mekka entstand vermutlich als Lagerplatz von Handelskaravanen und diente schon in vorislamischer Zeit als Pilgerstätte. Es lag an der Weihrauchstraße vom Süden kommend nach Ägypten und es gab Abzweigungen für die Handelskarawanen nach Dschidda sowie nach Osten zum Persischen Golf und nach Mesopotamien.
Ab wann von einer andauernden Besiedlung gesprochen werden kann, ist nicht bekannt. Es wird aber vermutet, dass bereits einige Generationen vor Mohammed ein Handelsplatz entstand. Der Koran beschreibt Mekka als einen Ort, der wegen seiner Trockenheit als Siedlungszentrum wenig geeignet ist.
Laut islamischen Quellen soll Mekka besiedelt worden sein, als der Stammesvater Abraham seine Frau Hagar und den gemeinsamen Sohn Ismail an diesen Ort brachte. Er bat Gott darum, seine Familie zu versorgen und ihnen die Herzen der Menschen zugeneigt sein zu lassen.
Koran Sure 14, Vers:37: Unser Herr, ich habe (einige) aus meiner Nachkommenschaft in einem Tal ohne Pflanzungen bei Deinem geschützten Haus wohnen lassen, unser Herr, damit sie das Gebet verrichten. So lasse die Herzen einiger der Menschen sich ihnen zuneigen und versorge sie mit Früchten, auf dass sie dankbar sein mögen.
Der weitere Verlauf dieser Sage: „Als die Wasservorräte zu ende gingen, lief Hagar insgesamt sieben Mal zwischen den Hügeln Safa und Marwa hin und her, um nach Wasser oder Karawanen Ausschau zu halten. Nachdem sie zu ihrem Zelt zurückkehrte, fand sie neben ihrem Sohn Ismail eine sprudelnde Quelle vor, die bis heute existiert und unter dem Namen Zam Zam bekannt ist. Die Karawanen, aus dem Jemen kommend, wußten, dass es in diesem Tal normalerweise kein Wasser gab, und wunderten sich, als sie Vögel über dem Tal kreisen sahen. Dies ist ein Zeichen dafür, daß es Wasser gibt. So suchten sie das Tal auf und fanden Hagar und ihren Sohn Ismail. Sie baten um Erlaubnis, sich dort niederlassen zu dürfen und somit begann die Besiedlung Mekkas. Ismail heiratete später eine Frau aus einem der jemenitischen Stämme. Als Abraham später nach Mekka zurückkehrte, errichtete er gemeinsam mit Ismail die Kaaba, zu welcher bis heute jährlich Millionen Menschen pilgern.“
Der Lauf zwischen den Hügeln Safa und Marwa ist ein fester Bestandteil der islamischen Pilgerfahrt. Historische Hinweise auf den Wahrheitsgehalt dieser Sage gibt es nicht, selbst die Existenz Abrahams als historische Person ist ungesichert.
Im Jahr 630 unterwirft sich die Stadt Mohammed, der seit 623, nach seiner Auswanderung nach Yathrib (Medina), mehrfach kriegerische Auseinandersetzungen mit Mekka hatte.
Der Einzug in Mekka verlief jedoch nicht kriegerisch und mit Waffengewalt, sondern friedlich und auf Grund eines vor Jahren abgeschlossenen Vertrages.