Abd ar-Rahman I (731–788) był ostatnim ocalałym z dynastii Umajjadów, wymordowanej przez Abbasydów w Damaszku. Uciekł przez Afrykę do Hiszpanii i w 756 r. został emirem Kordoby. Założona przez niego dynastia rządziła al-Andalus przez prawie trzy stulecia. W 785 r. zaczął budowę meczetu w miejscu wcześniejszego chrześcijańskiego zespołu kościelnego, tradycyjnie zwanego bazyliką św. Wincentego. Budowniczowie wzięli kolumny z ruin rzymskich i wizygockich, a że były za niskie, postawili na nich drugi rząd łuków. Tak powstał najbardziej rozpoznawalny motyw budowli: podwójne arkady, dolne podkowiaste i górne półkoliste, z klińcami na przemian z białego kamienia i czerwonej cegły.

Kolejni władcy rozbudowywali meczet: Abd ar-Rahman II w IX w., al-Hakam II (panował 961–976), uczony kalif i bibliofil, który w 971 r. dodał mihrab ozdobiony złotymi mozaikami w stylu bizantyjskim; według kronik cesarz w Konstantynopolu przysłał do tej pracy mistrza i materiał. W końcu, w latach 987–988, meczet poszerzył Almanzor (ok. 938–1002), wszechwładny hadżib, który w imieniu kalifa Hiszama II rządził al-Andalus i krwawymi wyprawami na chrześcijańską północ na pewien czas zatrzymał rekonkwistę. W szczycie meczet zajmował ok. 23 400 m² i był po Mekce największym meczetem świata, z około 850 kolumnami z jaspisu, onyksu, marmuru i granitu. Ciekawostka: mur kibli, wskazujący kierunek modlitwy, nie jest zwrócony ku Mekce, tylko wyraźnie na południe. Jedna z hipotez mówi, że budowniczowie powtórzyli kierunek meczetów Damaszku, skąd pochodzili Umajjadzi. Almanzor zabrał z Santiago de Compostela dzwony katedry, które według przekazów zawisły w meczecie jako lampy. Gdy w 1236 r. Ferdynand III Święty (zm. 1252), król Kastylii i León, zdobył Kordobę, kazał je zwrócić do Santiago.

Po rekonkwiście meczet zamieniono w katedrę, ale długo nie ruszano jego struktury. Dopiero w 1523 r. biskup Alonso Manrique zaczął budowę renesansowej katedry w samym środku lasu kolumn. Rada miasta protestowała, a cesarz Karol V (1500–1558), władca Hiszpanii, Niderlandów i Rzeszy, który zgodę wydał, miał po zobaczeniu efektu powiedzieć: „Zniszczyliście to, co było jedyne na świecie, a postawiliście to, co można zobaczyć wszędzie”. Anegdotę tę przytacza m.in. Théophile Gautier (1811–1872), francuski poeta, który w 1840 r. przemierzył Hiszpanię i porównał wnętrze meczetu do lasu pod dachem. Dziś ta mieszanina stylów to właśnie najbardziej niezwykła cecha budowli. W 2024 r. odwiedziło ją rekordowe 2,18 mln osób.