Der Überlieferung nach befand sich an der Stelle der heutigen Moschee-Kathedrale von Córdoba ursprünglich eine christliche Kirche, die dem Heiligen Vinzenz dem Märtyrer geweiht war und nach der islamischen Eroberung der Iberischen Halbinsel zwischen Christen und Muslimen geteilt wurde. Als die islamische Bevölkerung wuchs, beschloss der Amir Abderraman I. im Jahr 785, das gesamte Bauwerk zu kaufen und abzureißen, um die neue Moschee zu errichten. Im Gegenzug gestattete er den Christen, andere zerstörte Kirchen wieder aufzubauen, darunter die der Märtyrer Faustus, Januarius und Martial, die zu jener Zeit sehr verehrt wurden.

Die Historizität dieser Ereignisse ist umstritten, da es nur wenige archäologische Beweise gibt und diese nicht durch Ereignisse nach Abderramans Ankunft auf der Halbinsel verifiziert werden können. Der Bericht über die Umwandlung der Kirche in eine Moschee, der von dem Historiker al-Razi aus dem 10. Jahrhundert entwickelt wurde, weist viele Ähnlichkeiten mit der muslimischen Eroberung Syriens auf, insbesondere mit dem Bau der Umayyaden-Moschee in Damaskus. Für die mittelalterlichen Historiker dienten diese Parallelen dazu, die Eroberung der Halbinsel durch die Umayyaden und die Aneignung des westgotischen Córdoba zu verherrlichen.1115 Eine andere Quelle aus dem zehnten Jahrhundert erwähnt eine Kirche, die im Zentrum der Moschee errichtet wurde, ohne näher darauf einzugehen.15 Eine aktuelle archäologische Ausstellung in der Moschee-Kathedrale zeigt Fragmente eines spätantiken oder westgotischen Gebäudes, die der Architekt Félix Hernández 1930 ausgegraben hatte, und betont den christlichen Charakter des Bauwerks.

Die Gründungsmoschee wurde von Abderraman I. erbaut, einem der letzten Mitglieder der Umayyaden-Dynastie, dem es gelungen war, nach dem Massaker an seiner Familie während des Abbasidenaufstands aus Damaskus zu fliehen und den abbasidischen Statthalter Yusuf ibn 'Abd al-Rahman al-Fihri in Córdoba zu besiegen, wodurch 756 das neue unabhängige Emirat gegründet wurde.

Der Bau der Moschee begann im Jahr 785 und wurde in weniger als zwei Jahren abgeschlossen. Diese sehr kurze Zeitspanne ist möglicherweise auf die Wiederverwendung von römischem und westgotischem (Träger-)Material zurückzuführen, insbesondere von Säulen und Kapitellen. Der Architekt ist unbekannt, obwohl syrische (Umayyaden), westgotische und römische Einflüsse bei der Gestaltung des Gebäudes festgestellt wurden. Zu den Maurern gehörten wahrscheinlich Einheimische und Syrer syrischer Herkunft. Überlieferungen und einigen schriftlichen Quellen zufolge war Abderraman persönlich für das Projekt verantwortlich, obwohl umstritten ist, inwieweit er persönlich Einfluss auf die Gestaltung der Moschee hatte.

Die Qibla-Wände von Moscheen sollten theoretisch nach Mekka ausgerichtet sein; die Moschee von Córdoba ist jedoch nach Süden ausgerichtet, während Mekka nach Südosten zeigt.3233 Diese Ausrichtung, anders als bei den Moscheen von heute, ist auf historische Meinungsverschiedenheiten über die richtige Richtung der Qibla-Wand in weiter entfernten islamischen Orten wie al-Andalus und Marokko zurückzuführen.

Amir Hisham I. vollendete das unvollendete Werk nach dem Tod von Abderraman I., indem er den Innenhof oder Sahn fertigstellte und das erste Minarett errichtete.2630 Dieses frühe quadratische Minarett wurde später von Abderraman III. abgerissen, der ein weiteres errichtete, das später teilweise abgerissen wurde und dessen Überreste vermutlich in den christlichen Glockenturm der Kathedrale eingelassen sind. Die Fundamente des Minaretts von Hisham I. wurden im 20. Jahrhundert von dem Archäologen Félix Hernández im Patio de los Naranjos gefunden, der den Standort auf dem Pflaster markierte, so dass er heute noch sichtbar ist.

Die klassische Geschichtsschreibung geht davon aus, dass mit dem Wachstum der Stadt ein Oratorium (Haram) mit größerem Fassungsvermögen benötigt wurde, um mehr Gläubige während des Freitagsgottesdienstes aufnehmen zu können, so dass Abderraman II. beschloss, die Moschee erstmals zu vergrößern. Die Arbeiten begannen 836 (obwohl auch die Jahre 833 und 848 erwähnt werden) und wurden 852 unter der Herrschaft des Sohnes von Abderraman II., Muhammad I. (reg. 852-886), abgeschlossen.292630 Die ursprüngliche Quibla-Mauer wurde abgerissen, deren Überreste noch heute in Form von großen Säulen sichtbar sind, und die Arkaden wurden um acht weitere Joche mit einer Gesamtlänge von 24 m erweitert.

Im Jahr 929 gründete Abderraman III. das neue Kalifat von Córdoba und festigte die neue andalusische Macht in der Region. Im Rahmen seiner verschiedenen Bauprojekte vergrößerte er den Hof der Großen Moschee, riss das erste Minarett ab und errichtete ab 951-952 ein neues.2630 Das Minarett war 47 m hoch und hatte eine quadratische Grundfläche von 8,5 m auf jeder Seite. Der Gelehrte Jonathan Bloom hat vorgeschlagen, dass Abderramans Bau des Minaretts als Symbol für die wachsende Autorität des Kalifen und als Versuch, dem Fatimidenkalifat im Osten Konkurrenz zu machen, angesehen wurde. Abderraman verstärkte auch die Nordwand des Innenhofs, indem er eine weitere Fassade vor der alten anbrachte.

Parallel zum Glanz des Kalifats begann Al-Haken II (reg. AH 961-976), der sich an den architektonischen Projekten seines Vaters beteiligte, während seiner Regierungszeit (AH 961) mit dem innovativsten Ausbau. Er ließ den alten Mihrab von Abderraman II. abreißen, dessen Überreste auch heute noch zu sehen sind, und verlängerte die Gebetshalle um 45 m nach Süden, indem er die ursprüngliche doppelbogige Konstruktion um 12 Joche erweiterte. Das Mittelschiff der Moschee wurde durch den Bau einer gerippten Kuppel veredelt, die heute Teil der Villaviciosa-Kapelle ist. Außerdem wurde eine rechteckige Maksura mit drei gerippten Kuppeln um den neuen Mihrab herum errichtet, die von einzelnen, mehrfach gelappten und ineinander verschlungenen Bögen überragt werden. Die Säulen bestehen abwechselnd aus rosafarbenen Schäften aus rotem Jaspis aus Cabra und aus dunkelblauen Säulen aus der Sierra Morena von Córdoba.

In Anbetracht des kontinuierlichen Bevölkerungswachstums von Córdoba beschloss Almanzor, der Hajib des Kalifen Hisham II, zwischen 987 und 988 die dritte und letzte Erweiterung der Moschee vorzunehmen.2629 Es handelte sich um die umfangreichste Erweiterung, die sowohl den Innenhof als auch den Gebetssaal betraf, auch wenn sie aufgrund der Nähe zum Fluss Guadalquivir nicht wie die vorangegangenen nach Süden, sondern um 47,76 m nach Osten vorgenommen wurde, wodurch die Moschee um acht Schiffe erweitert wurde und der Mihrab nicht mehr in der Mitte stand. Auch beim Neubau wurde das gleiche doppelbogige Muster wieder verwendet, wobei sich die Vouten nur farblich, nicht aber vom Material her unterscheiden, da sie alle aus Kalkstein bestehen, wobei die roten Vouten mit Almagra bemalt sind.

Nach dem Zusammenbruch des Kalifats von Córdoba zu Beginn des 11. Jahrhunderts wurden an der Moschee keine weiteren Anbauten vorgenommen. Die fehlende Autorität hatte negative Folgen für den Tempel, wie Plünderungen und Schäden während der Fitna von al-Andalus.47 Córdoba erlitt ebenfalls einen Niedergang, obwohl es ein wichtiges kulturelles Zentrum blieb. Unter den Almoraviden wurden kordobanische Handwerksbetriebe beauftragt, reich verzierte Mimbars für wichtige Moscheen in Marokko anzufertigen. Das berühmteste ist das Mimbar von Ali Ibn Yusuf aus dem Jahr 1137, das von dem Mimbar der Großen Moschee von Alhaken II. inspiriert wurde.

Nach der Eroberung Córdobas durch die Kastilier im Jahr 1236 ließ Ferdinand III. von Kastilien die Moschee in eine Kathedrale umwandeln und weihte sie der Jungfrau Maria, wobei verschiedene Veränderungen vorgenommen wurden, die schließlich die heutige Kathedrale von Córdoba prägten. Die erste Messe wurde am 29. Juni desselben Jahres gefeiert. Laut Bischof Rodrigo Jiménez de Rada gab Ferdinand III. auch die alten Glocken der Kathedrale von Santiago de Compostela, die von Almanzor entwendet worden waren, als symbolischen Akt an die Stadt zurück.

Der größte Bruch mit dem islamischen Bauwerk fand jedoch im 16. Jahrhundert statt, als unter den künstlerischen und architektonischen Auspizien der Renaissance ein großes christliches Kirchenschiff in der Mitte der alten Moschee errichtet wurde, das die neue Hauptkapelle bildete; dies stellte einen gravierenden Bruch mit den islamischen Raumpostulaten dar. Der Vorschlag von Bischof Alonso Manrique war umstritten und stieß auf den Widerstand des Gemeinderats von Córdoba. Schließlich setzte sich Kaiser Karl V. dafür ein, dass die Arbeiten durchgeführt werden konnten, auch wenn er es später bedauerte, wie Bernardo de Alderete sagte: "Du hast zerstört, was einzigartig auf der Welt war, und an seine Stelle gesetzt, was man überall sehen kann".

Im Jahr 1816 wurde der ursprüngliche Mihrab der Moschee freigelegt, nachdem das Altarbild aus der ehemaligen Peterskapelle entfernt worden war. Patricio Furriel war für die Restaurierung der islamischen Mosaike des Mihrab verantwortlich, einschließlich der verlorenen Bereiche. Auch an der alten Struktur der Moschee wurden zwischen 1879 und 1923 unter der Leitung von Ricardo Velázquez Bosco Restaurierungsarbeiten durchgeführt, bei denen unter anderem die barocken Elemente, die der Kapelle von Villaviciosa hinzugefügt worden waren, entfernt und die früheren Strukturen freigelegt wurden. Während dieser Zeit, im Jahr 1882, wurde der Tempel zum Nationaldenkmal erklärt. Anschließend wurden zwischen 1931 und 1936 von Félix Hérnandez archäologische Ausgrabungen im Gebetsraum und im Hof der Orangenbäume durchgeführt. Spätere Wissenschaftler haben festgestellt, dass sich diese Restaurierungen ab dem 19. Jahrhundert auf die Wiederherstellung der islamischen architektonischen Elemente konzentrierten, da Spanien ab dem 19. Jahrhundert große Anstrengungen unternahm, seine andalusischen Denkmäler zu studieren und wiederherzustellen.