यह इमारत विसिगोथ मूल के लोगों द्वारा गिरजा के रूप में सेंट विन्सेंट को शर्धांजली के तौर पर बनाई गई थी।[1][2] मुस्लिम शासकों द्वारा विसिगोथ राज्य पर क़ब्ज़ा जमाने के पश्चात इस इमारत को दो भागों में बाँट दिया गया - एक मुस्लिम और दूसरा ईसाई। वनवास में घूम रहे उमय्यद शहज़ादे अब्द अल-रहमान प्रथम ने किसी तरह अपनी जान बचाते हुए आईबीरिया पहुँच गया। इसके पश्चात वह अल-अन्दलुस के राज्यपाल युसुफ़ अल-फ़ीहरी को पराजित करने में कामयाब रहा। अब्द अल-रहमान प्रथम ने पाया कि कोरदोबा विभिन्न विश्वास पर आधारित धार्मिक गुटों में बट चुका है जिनमें ग्नास्ती, प्रिसिल्लानी, दोनाती और लूसिफ़ेरी शामिल थे। उसका दृड़ संकल्प था कि एक ऐसा प्राथना स्थल का निर्माण हो जो शानोशौकत के मामले में बग़दाद, येरुशलम और दिमिश्क़ का मुक़ाबला कर सके और धार्मिक महत्व के मामले में मक्का की तरह पवित्र माना जाए। ईसाई गिरजा घर उसी स्थल पर स्थित था जहाँ रोमन सभ्यता के अनुसार जानूस देवता को समर्पित एक मन्दिर किसी समय पर रहा करती थी। अब्द अल-रहमान अपनी मस्जिद का निर्माण उसी स्थान पर चाहता था। उसने पराजित ईसाइयों से उस गिरजा घर और स्थल ख़रीदने की पेशकश की। समझौता तय कराने का कार्य सुलतान के विशेष सचिव उमेया इब्न यज़ीद को सौंपा गया। समझौते के अंतरगत ईसाई समुदाय को सेन्ट फ़्रान्सिस, सेन्ट जानुआरिस और सेन्ट मार्सेल्लूस को समर्पिर गिरजा घरों के पुनः निर्माण की अनुति दे दी गई थी जिन्हें वीर गति को प्राप्त होने के कारण ईसाई अति महत्वपूर्ण समझते थे। [3]

अब्द अल रहमान ने ईसाइयो उनके को बर्बाद हो चुके धार्मिक स्थलों के पुनर्निर्माण करने की अनुमति दी और इस कार्य के बदले उसने सेन्ट विंसेंट के गिरजा घर के आधे हिस्से को ईसाई से खरीदा। [4][5] ख़लीफ़ा का ख़ज़ाना मालामाल था। यह ख़ज़ाना हाल के युद्धों के दौरान गोथ लोगों से छीन ली गई दौलत के अलावा वह देश की धर्ति की उपज पर एक दशमांश निकाले और उसी प्रकार का कर उत्पाद पर लगाया। अन्दलूसिया में मुसलमान ज़कात के कर का भुगतान करने के लिए बाध्य किया गया और जज़्या के रूप में एक कर ईसाइयों और यहूदियों पर लगाया कि वे विदेशी आक्रमणकारियों से अन्दलूसिया में सुरक्षित रह सकें। इसके अलावा, मुस्लिम शासक बहुत से आइबेरिया के मूल्यवान खानों, संगमरमर की खदानों, और धन के अन्य स्रोतों के अधिग्रहण से समृद्ध हो चुके थे। इन राजस्व द्वारा अब्द अल रहमान और उनके उत्तराधिकारियों, हिशाम, अब्द अररहमान द्वितीय, जो इस शाही ख़ानदान के सर्वोच्च और कड़ी में तीसरे रहे थे, अल मनज़र ने, मस्जिद के निर्माण में ख़ूब पैसा ख़र्च किया था। [3]

अब्द अल रहमान प्रथम ने हज़ारों मेज़क्वीटा में हज़ारों कारीगरों और मज़दूरो को काम पर लगाया था। इतना तेज़ रफ़्तार काम था कि इससे ज़िले के सभी संसाधनों का ख़ूब विकास हुआ। बड़े-बड़े पत्थर और अति-सुन्दर काम वाले संगमरमर के पत्थर सिएरा मोरेना और के आस-पास से लाए गए थे। विभिन्न प्रकार के धातु ज़मीन से खोदकर लिकाले गए थे और इसी कारण से कोरदोबा में कई नए कारख़ाने सामने आए और शहर के उत्पाद जगत में एक नए उत्साह का अनुभव किया गया था। सीरिया का प्रसिद्ध निर्माण-विशेषज्ञ के मस्जिद की योजना तय्यार की। कोरदोबा के किनारे स्थित अपने निवास महल का त्याग करके ख़लीफ़ा शहर में आकर बख गया, ताकि सभी कार्यों की वह व्यक्तिगत समीक्षा कर सके और निर्माण की रूप-रेखा पर अपनी राय दे सके। अब्द अल रहमान प्रथम ने काम करने वालों के बीच अपना आना जाना रखा और उन्हें हर दिन कई घन्टे काम करने का आदेश दिया। [3]

यह मस्जिद बाद में कई परिवर्तनों से हो कर गुज़री। अब्द अल रहमान द्वितीय ने एक नए मीनार के निर्माण का आदेश दिया जबकि 961 में अल हकम द्वितीय ने पूरी इमारत में फैलाव लाए और मेहराब को एक नया सुन्दर रूप दिया। अल मंसूर इब्न अबी आमिर ने अंतिम सुधार लाया। यह एक उभरी हुई पदचालक-मार्ग बनाई गई जिससे कि ख़लीफा के महल से इस मस्जिद को जोड़ दिया गया था जैसे कि अधिकांश रूप से मुस्लिम शासकों की परंपरा रही थी। ईसाई शासकों ने बाद में यही परम्परा को अपनाकर गिरजा घरों के निकट अपने महल का निर्माण किया और उसी प्रकार की उभरी हुई पदचालक-मार्गों का निर्माण किया। 987 में अपने वर्तमान आयामों पर यह परिसर पहुँच गया था जब बाहरी स्तम्ब और अन्दर के खुले मैदानों का निर्माण पूरा हुआ।