Pembinaan Mezquita (asal namanya Masjid Aljama) berjangka lebih dari dua abad, bermulanya pada 784 M di bawah penyeliaan Amir Muslim pertama Abd ar-Rahman I, yang menggunakannya sebagai sebuah tambahan ke istananya dan menamakannya sebagai penghormatan kepada isterinya. Tapak itu sebelum itu adalah sebuah katedral Visigoth St. Vincent. Apabila tentera Tariq ibn-Ziyad pertama kali menduduki Córdoba pada 711, mereka dan penganut Kristian berkongsi ruangan katedral, menurut sejarawan ar-Râzî, yang mendokumentasikan sejarah masjid. Tetapi dengan penubuhannya Umayyad dalam buangan negara sebagai emir-emir Córdoba, tolak-ansur itu tidak lagi cukup. Perbincangan di antara Emir dan biskop Córdoba, diberikan janji bayaran besar wang dan juga izin untuk membina semula salah satu gereja-gereja luar yang telah diruntuhkan semasa penaklukan, mendorong penganut Kristians bersetujukan melepaskan bahagian St. Vincent mereka, yang telah dirobohkan dan masjid baru, pada fasa pertamanya, dibina di atas asasnya (Wolf). Unik berbanding masjid-masjid lain, mihrabnya tidak mengarah terhadap Mekah. Beberapa penjelasan telah dicadangkan untuk menerangkan kedudukan masjid yang tidak mengikut peraturan agama. Sesetengah bercadang bahawa mihrab itu mengarah ke arah selatan kerana asas masjid menggunakan asas pembinaan Rom lama dan Visigoth. Yang lain pula menegaskan bahawa Abd ar-Rahman mengarahkan mihrab ke arah selatan seolah-olah baginda masih berada di ibu negara Umayyad dan tidak dibuang negara.

Masjid ini melalui beberapa pertukaran: Abd ar-Rahman III memerintahkan pembinaan menara baru, sementara Al-Hakam II, pada 961, membesarkan rancangan bangunan dan mengindahkan mihrab. Pembaharuan yang terakhir dijalankan oleh Al-Mansur Ibn Abi Aamir pada 987.

Masjid ini adalah yang termewah daripada 1,000 masjid lainnya yang berada di bandar tersebut, dan pada satu waktu masjid kedua terbesar di dunia Islam. Ia bercantum dengan istana Khalifah dengan tempat laluan yang dinaikkan, membenarkan pemerintah Cordoba untuk mengunjungi masjid tanpa risiko pembunuhan. Hari ini istana Biskop berdiri di tapak istana Khalifah.

Bandar tempat letak masjid ini telah ditakluki oleh beberapa serangan, dan setiap gelombang penaklukan menambahkan tanda mereka pada gaya seni bina. Bangunan tersebut dikenali dengan gerbang gergasinya, dengan lebih dari 1,000 tiang yang terbuat dari jasper, onyx, marmar dan granit. Ini dibuat dari kepingan-kepingan kuil Rom yang berada di situ sebelumnya, dan juga bangunan-bangunan Rom lain yang telah roboh. Gerbang "poly-lobed", digambarkan di atas, adalah pengenalan baru pada gaya seni bina, dan menolong menyokongkan berat besar siling yang lebih tinggi. Selain gerbang-gerbang berbentuk kasut kuda, Mezquita juga mempunyai cerukan dinding sembahyang yang kaya dengan celupan emas. Sebuah kubah pusat berbentuk sarang lebah mempunyai jubin biru dihias dengan bintang-bintang. Mihrabnya pula merupakan sebuah karya agung kesenian gaya seni bina, dengan corakan geometri dan aliran tumbuh-tumbuhan. Mezquita mencapai dimensi terbarunya pada 987 dengan penyelesaian ruang ibu di sebelah luar dan laman pokok oren.

Pada tahun (1236) apabila Cordoba ditakluk kembali dari orang Islam Moorish, oleh Raja Ferdinand III dari Castile dan menubuhkan kembali Christendom, masjid itu ditukar menjadi sebuah gereja Kristian. Ini adalah perkara yang biasa pada era itu. Hagia Sophia di Constantinople, misalnya, telah ditukarkan menjadi sebuah masjid pada hari tentera Uthmanniyah memasuki bandar itu. Parthenon pada Acropolis Athens telah dijadikan sebuah kuil Athena, gereja dan masjid. DI Semenanjung Iberia, adanya bangunan yang telah, mengikut pusingan, menjadi sinagog, masjid, gereja, dengan sesetengah pertukaran tangan berkali-kali. Alfonso X menyelia pembinaan Chapel Villaviciosa dan Chapel Diraja di dalam struktur masjid, tetapi kemudian merobohkan kembali tambahan ini. Raja-raja yang berikut membina tambahan lebih berciri-ciri Kristian kemudian: Enrique II membina kembali chapel pada abad ke-14.

Perubahan yang paling jelas adalah pembinaan nave katedral Pembaharuan di tengah-tengah struktur. Ia telah dibinakan dengan keizinan Carlos V, raja kesatuan Sepanyil; setelah baginda melihat apa yang telah dibinakan, baginda mengatakan, "Kamu telah membina apa yang kamu atau yang lain telah bina di tempat lain, tetapi kamu telah merosakkan sesuatu yang unik di dunia." Walau bagaimanapun, penambahan nave katedral dipercayai telah mengukuhkan kestabilan struktur binaan [perlu rujukan], dan penukarannya ke sebuah gereja Kristian (pada rasminya Katedral Assumption Dara) telah membantu untuk mengekalkannya ketika Pasitan Sepanyol masih sangat aktif. Walau bagaimanapun, ia diakui bahawa penduduk tempatan, Kristian lama dan mualaf bersama, dengan gigih mempertahankan tugu itu setelah bandar itu dirampaskan semula oleh raja-raja Kristian.

Para ahli seni dan gaya seni bina telah bersambung untuk menambahkan pada struktur terkini sehingga lewat abad ke-18.

Pada 1931, Dr. Allama Muhammad Iqbal adalah orang Islam pertama untuk bersolat di dalam Mezquita setelah penutupannya ke Islam. Biskop Juan Jose Asenjo, telah menolak keizinan orang Islam untuk bersolat di Mezquita.