Cuenta la tradición que los cristianos que habitaban Madrid en el siglo VIII, escondieron la imagen de la Virgen en un cubo de la muralla para evitar que fuera destruida ante la invasión de los sarracenos.
Pasado largo tiempo, el 9 de noviembre de 1085, durante el mandato del Papa Gregorio VII, se organizó una procesión en torno a la muralla. En aquel momento, se desprendieron varias piedras del muro quedando al descubierto la imagen de la Virgen de la Almudena que había estado escondida durante tantos siglos.
Fue el conde duque de Olivares en el siglo XVII quien promovió la edificación de un templo donde se venerase a la Virgen de la Almudena como patrona de Madrid. Y en 1646 la Almudena se convierte a en patrona de la villa, siendo "protectora e intercesora para siempre jamás" de la capital.
Finalmente, en 1908, el papa Pío X declara a la Almudena patrona de Madrid por soberano decreto y queda fijada la fecha de su festividad, el 9 de noviembre.