Tras bastantes años de lucha política, Abd al-Rahman logra asentar su poder en Córdoba y decide la creación de una mezquita del estilo de su corte y que simbolizara la solidez de su nuevo reino independiente. Tras la conquista musulmana se había llegado a un acuerdo con los visigodos, por el que se les dejaba conservar la religión sin llegar al alarde del culto, y los árabes podrían reconstruir los edificios cordobeses derribados en la conquista. Así, los edificios cristianos existentes se repartieron, Abd al-Rahman compró, se cree que por una considerable suma de dinero, “ochenta mil monedas de buen peso”, la basílica visigoda de San Vicente, pequeño edificio de tres naves y con ábside en la cabecera. En el año 785, el califa derriba la basílica y da comienzo a las obras de su mezquita. 

Al año siguiente ya estaba terminada. La rapidez en su construcción viene dada por el gran empeño que tenía Abd al-Rahman en tener un gran edificio en su corte, para ello utilizó bastante mano de obra, y además contó con un buen ahorro de tiempo y trabajo al aprovechar materiales visigodos y romanos de otras edificaciones, e incluso de otros lugares como Toledo. Esto tuvo como consecuencia la falta de uniformidad, sobre todo en los capiteles de las columnas, pero también se logró así mayor enriquecimiento  decorativo, contribuyendo a uno de los caracteres que se va a desarrollar en la arquitectura musulmana: el aprovechamiento y la variedad de elementos.

Por su procedencia, Abd al-Rahman tenía conocimiento de la mezquita de Damasco, y mandó a los arquitectos que construyeran la de Córdoba siguiendo el ejemplo de la primera. Su autoría está sin descubrir, lo más probable es que la traza general fuera idea del propio emir o sus consejeros, ya que el edificio muestra el esquema más simple de todos los conocidos.
 
 

 La mezquita responde al tipo llamado Aqsa; el espacio destinado a sala de oración, con unas medidas de setenta por treinta y siete metros y un aforo de diez mil personas, constaba de once naves en dirección norte-sur, aprovechando el muro de la epístola de la iglesia cristiana, que se convirtió en qibla, y de doce tramos, quedando la nave central más ancha y alta que las del resto, y las laterales estrechándose paulatinamente. Sobre el número de naves en el haram, existen discrepancias: Lambert y Lévi-Provençal opinan que habría nueve naves, Gómez Moreno, por su parte, lo considera un error que se repite en todos lo documentos, considerando que había once y que las dos últimas estarían cerradas al ser ocupadas por las mujeres. 

 La orientación del muro de qibla ofrece una irregularidad, al estar orientada hacia el sur y no hacia el sureste. La explicación se encuentra en la influencia de las mezquitas de Siria, que tenían la Meca en esta dirección, o porque para dirigirse en peregrinación a la Meca debían tomar el 
camino del sur.
 
 

En el interior del haram se adoptó una solución absolutamente original para resolver el problema de la altura: la de un doble orden, columnas en la parte baja y pilares sobre cimacio, en la  superior. Dos filas de arcos articulan el espacio interior, de herradura entre las columnas, actuando como arcos de  entibo, y entre las pilastras, de medio punto, soportando éstas la techumbre de madera, a doble vertiente, y los canalillos de desagüe. Los arcos de herradura son de proporción visigoda, abiertos, lo que hace pensar en una mano de obra local. Para salvar  la diferencia entre el pilar y el cimacio, se pone un modillón de cinco rollos, llamado así por Gómez Moreno, muy característico y propio de esta mezquita. Esta idea del doble arco ya se había visto en Damasco, pero la manera de construirlo, dejando las albanegas libres, con el arco al aire, es único de Córdoba, igual que la superposición de soportes, que se encuentra en otras mezquitas omeyas, como la de Amr en Fustat, en Egipto y la gran mezquita de Qairawan, en Túnez, aunque no con la compleja y airosa solución que se adopta aquí.

Las columnas tenían basa y cimentación independiente, lo que ha motivado, a lo largo del tiempo, que cada una reaccionara de distinta manera, produciéndose desniveles entre ellas. En las siguientes ampliaciones de la mezquita, la cimentación será corrida para cada fila de arquerías. 

Los fustes eran de mármol y granito,  los de la nave central de  pudinga rosada, algunos presentan estrías verticales o en forma de espiral.

 El precedente de esta idea tan original se ha querido ver en los acueductos romanos, más concretamente en el de los Milagros de Mérida. También de este antecedente ha podido adoptarse la utilización de la fábrica mixta de piedra y ladrillo rojo, lo que da al interior su característico cromatismo. Por otra parte, en la última etapa de la Antigüedad se encuentran revestimientos de dovelas coloreadas de opus sectile. Además del sentido estético, esta bicromía en la utilización del material tuvo sus ventajas económicas y estructurales, ya que al ser materiales de distinta elasticidad, se acomodaban unos con otros cuando había movimientos en el muro. Esta bicromía se hace tan común que se va a fingir en puertas y otrss edificios.

Su articulación interior junto al poco tiempo que tardó en ser construida llevaron a algunos estudiosos, entre ellos Lambert, a la polémica de que en este primer período de tiempo sólo fuera construido el primer piso de arcos, por pensar en un edificio más bajo. Otras investigaciones descartan esta hipótesis, afirmando que desde un principio la construcción estuvo pensada tal y como se llevó a término.

 La única iluminación que le entraba al haram era la de dos vanos que se abrían al patio. Se sabe, por documentos, de la existencia de una puerta a la izquierda, que no se conserva, y otra en el lateral derecho, prototipo de fachada de otros edificios, llamada Bab al-Wuzara, posteriormente fue la de San Esteban. Objeto sobre el que existe polémica de si corresponde a esta época de Abd al-Rahman I o de Muhamed I. 

Hay documentos que hablan de su existencia desde tiempos del primer emir, pero en la puerta se leía la fecha 853, casi un siglo después de Muhamed I. Esta duda cronológica adelanta o atrasa su datación cien años. Su estructura tripartita y las hornacinas son del primer momento, lo que plantea más  problemas es el arco de herradura y el alfiz. El arco tiene un peralte de medio radio, a medida que avanza la cronología se va cerrando, aquí es posterior en diseño; los especialistas han pensado que lo que se hace es rehacer el arco e incorporar algunas novedades decorativas.

La puerta se abre en el lado oeste de la mezquita. Se articula entre dos torres laterales y se divide en tres calles, la central más ancha con vano de entrada, que tiene arco de herradura y dintel, encuadrado todo ello por alfiz. El arco está enjarjado, las dovelas del arranque se disponen de forma horizontal hasta la altura de los riñones, en que se despiezan de forma radial al centro del arco. Este arco esta cubierto de falsas dovelas que son, alternativamente, relieves de ladrillo y estuco con decoración vegetal. El trasdós del arco va bordeado por una línea decorativo, que algunos autores han asemejado con una arquivolta, y que encuadra también al alfiz. Sobre el vano se dispone un andén de tres arcos de herradura ciegos. La parte superior se cubre con un guardapolvo con modillones.

Las calles laterales tienen en la parte inferior un vano ciego adintelado. Sobre él hay un nicho con dintel escalonado, de influencia romana, y por encima hay un vano abierto con un arco de herradura de descarga, decorado con celosías, con formas geométricas simples, probablemente visigodas de la basílica de San Vicente. Como se aprecia la organización general es similar a los arcos de triunfo y puertas de palacios romanos.

De esta primera construcción, se ha conservado intacto el muro occidental, el sur y el este desaparecieron con las sucesivas ampliaciones, y el lado norte, el que abría al patio, fue reforzado y ocultado por otro muro en el año 958 con las obras acometidas por Abd al-Rahman III.

A la muerte de Abd al-Rahman I no se habían concluido las obras, continuándolas su hijo Hisam I, que añadió algún otro elemento a la construcción. En el lado norte construyó unas galerías para la oración de las mujeres, también dotó al edificio de una fuente o pila de abluciones,  y de un alminar, hoy desaparecido. De este último se sabe de su existencia por estudios de infrarrojos. Tuvo medidas cuadradas, seis por seis, y respondía al tipo de torre dentro de torre. Su altura pudo ser de hasta dieciocho metros.