Junto a este lugar se situó hasta 1569 la PUERTA O ARCO DE SANTA MARÍA perteneciente a la muralla de La Almudena, fortaleza del Madrid musulmán.
Esta Puerta pertenece al primer recinto de la muralla islámica del siglo IX mandada construir por Mohamad I de Córdoba entre 860 y 866. Su nombre en el Madrid árabe se desconoce, aunque se especula si pudo llamarse de Guadalajara por ser la población más importante en su destino de salida.
Junto a esta Puerta estaba la Mezquita. Los documentos del Siglo X hacen pensar que Madrid fue un lugar de concentración militar o “ribat” de la Marca Media donde podía cumplirse el deseo del Profeta de la Yihad, o Guerra Santa, contra los levantamientos de los mozárabes y a veces de los árabes del Norte.
Este lugar debió ser inicialmente un lugar de culto visigodo dedicado a la Madre de Dios antes de convertirse en mezquita. Después de la conquista de Alfonso VI se transformó en la Iglesia de Santa María, lugar esencial de la devoción mariana de la Villa de Madrid, donde se dio culto a Nuestra Señora de la Flor de Lys y luego a la Virgen de la Almudena. La tradición dice que los visigodos escondieron la imagen de María en un cubo de la Muralla al venir los árabes a la Península, pero en ese caso debió de ser escondida en un muro anterior a ellos, pues ha desaparecido.
En 1629 Gerónimo de la Quintana cuenta cómo era y cómo se produjo su dura demolición: “Miraba al Oriente… Era una torre fortísima de pedernal, cuya fortaleza se experimentó en la dificultad que tuvieron muchos oficiales para desencajar la cantería de ella, cuando por ensanchar aquel paso se derribó, y debía ser angosta, pues fue necesaria su ruina para la comodidad del paso… En lugar de esta puerta que derribaron, en el mismo sitio hicieron un arco grande, que llamaron de la Almudena, por una santa imagen de Nuestra Señora que se venera en la Iglesia Mayor del mismo apellido.”
En 1572 fue derribada con motivo de la entrada real de Ana de Austria.
