Secondo un'antica leggenda, “quando l'apostolo Giacomo venne da Gerusalemme per evangelizzare la Spagna, portò ai Reali di Madrid la statua miracolosa oggi nota come l'Almudena” (secondo un manoscritto del 1640).
Nella sua determinazione a trovare la statua originale, il re Alfonso VI organizzò una processione guidata dalla famiglia reale, dal clero, dalla nobiltà e dal popolo di Madrid intorno al muro, vicino all'“almudith” (un deposito di grano che i Mori chiamavano “Almud”, misura), quando un mucchio di pietre cadde in un secchio vicino, esponendo la nicchia che nascondeva la statua della Vergine, da allora chiamata Almudena.
La gente rimase meravigliata nel vedere che le due candele accanto a lei erano rimaste accese per tre secoli, il che spiega il volto “scuro” della statua. Dal 9 novembre 1085, la Vergine dell'Almudena è considerata la patrona di Madrid. Questa statua è certamente precedente all'anno 712, quando fu nascosta durante la conquista islamica.