Nach der Hidschra, dem Auszug aus Mekka im Jahre 622, wurde Medina der Sitz von Mohammeds anwachsender Bewegung. Seine damalige Moschee und sein Wohnhaus stellen heute einen Teil der „Moschee des Gesandten“ dar. 622 wurde Mohammed von Abgesandten der Aus und Chasradsch nach Yathrib (früherer Name Medinas) eingeladen, um als eine Art Gouverneur zu wirken. Medina war damals eine geteilte Stadt: Unterschiedliche Clans und Religionen lagen in Zank und Streit. Mohammed bewirkte eine Einigung in der Stadt. Alle Beteiligten stimmten einem Pakt zu, der von Mohammed und von seinen Schülern aufgestellt wurde. Er lud die gesamte Stadt ein, der neuen Religion, dem Islam, zu folgen, jedoch konnte er die meisten Juden nicht überzeugen. Unter den arabischen Neumuslimen opponierten die nur scheinbar konvertierten „Heuchler“ um Ibn Ubayy und paktierten mit den Juden Medinas. Die Banu Nadir und die Banu Qainuqa wurden daraufhin vertrieben und bei den Banu Quraiza wurden alle Männer ausgerottet und die Frauen und Kinder versklavt.
Nach Änderung der Qibla von Jerusalem gen Mekka hielt eine kleine Gruppe konvertierter Juden an der ursprünglichen Qibla fest. Sie wurde die Sekte der Qibla al-Qudsiyya genannt.
Während der zehn Jahre nach der Hidschra bildete Medina das Zentrum des islamischen Lebens, bis Mohammed Mekka eroberte. Noch als die islamische Führung dort etablierte wurde, blieb Medina für einige Jahre die wichtigste Stadt des Islam und de facto die Hauptstadt des Kalifats.
Unter den ersten vier Kalifen, den Rechtgeleiteten Kalifen, erweiterte sich das islamische Reich schnell und umfasste bald Jerusalem, Ktesiphon und Damaskus. Nach dem Tod von Ali ibn Abi Talib verlegte der erste Umayyaden-Kalif Mu'awiya die Hauptstadt nach Damaskus. Medina hat heute noch große religiöse Bedeutung als zweitwichtigster islamischer Wallfahrtsort.
1924 wurde Medina, das Jahrhunderte nominell zum osmanischen Reich gehört hatte, von Ibn Saud erobert, dessen Reich später zu Saudi Arabien wurde.