L’etimologia della parola Almudena ha un’origine araba (dal 711 al 1492 la Spagna era sotto la dominazione araba). La prima che viene in mente è «al-mudayna», diminutivo di Medina, la città dell’Arabia Saudita ma esisterebbe anche un’altra origine a partire da «almudith», deposito di grano, o «Almud», misura (di grano).
È da notare che l’appellativo antico, prima della conquista musulmana, era «Maria la grande» (Santa Maria la Mayor).
Sono numerose le tradizioni a proposito dell’origine di questo santuario, quella più conosciuta narra che la statua della vergine di Almudena fu nascosta in un muro nel 712, all’inizio della conquista musulmana. Con la riconquista (la reconquista), nel 1085, il re Alfonso VI di León la fece cercare. Alcune pietre del muro crollarono e riportarono alla luce la statua con due ceri ancora accesi nonostante fossero trascorsi diversi secoli.
Un’altra tradizione riporta un’apparizione mariana all’eroe castigliano Rodrigo Díaz de Vivar, chiamato il «Cid».
Si racconta anche che la statua fu scolpita da Nicodemo, colui che incontrò Gesù di notte, che fu dipinta da san Luca e portata da san Giacomo… Difficile confermare tutto questo: il manoscritto che riporta gli eventi è del 1640! Comunque sia, la statua attuale è del 1500 ed è stata attribuita ad uno scultore dell’epoca, Diego Copín de Holanda.
Dal 1623, e riconfermata nel 1646, la Vergine di Almudena è la patrona di Madrid ed è festeggiata il 9 novembre. Nel 1885, il papa Leone XIII con una bolla papale decise di creare la diocesi di Madrid. Qualche decennio dopo iniziarono il lavori di costruzione della cattedrale, sede del vescovo. Fu così che si costruì Santa María La Real de La Almudena.
Il 15 giugno 1993 fu consacrata da Giovanni Paolo II durante il suo quarto viaggio in Spagna.