Amikor 1561-ben Madrid lett a Spanyol Királyság fővárosa az addigi Toledo helyett, az egyház központja továbbra is Toledóban maradt és az új fővárosnak nem volt katedrálisa. Már a 16. század elején voltak tervek egy templom építésére, amit az Almudénai Szűznek szántak volna. De ekkoriban a Spanyol Királyság már 40 várost építtetett az Új Világban, ahol ugyanígy voltak katedrálisok és erődítmények. A költségvetés első számú prioritása az volt, hogy a birodalom terjeszkedjen, Madrid katedrálisának építése pedig nem szerepelt ezek között. Mindegyik más spanyol városnak már évszázadok óta volt székesegyháza, de Madridnak csak régi, kis templomai voltak. Az Almudéna építése 1879-ben kezdődött el.
A katedrális ott építették volna fel, ahol egy mecset állt és 1083-ban lerombolták, amikor VI. Alfonz vezetésével visszahódították Madridot a móroktól.[1]
Francisco de Cubas, Cubas márkija vezette a neogótikus stílusban épülő katedrális építési munkálatait. Az építési munkálatok a spanyol polgárháború miatt megszakadtak, majd 1950-ben Fernando Chueca Goitia olyan terveket dolgozott ki, hogy a barokk homlokzat illeszkedjen a területen, szemben elhelyezkedő királyi palota fehér-szürke színével.
