Venía de antiguo la aspiración de que Madrid contara con una catedral, pero los diversos intentos previos fracasaron. La nueva construcción comienza a gestarse en 1868, cuando la Congregación de Esclavos de la Virgen de la Almudena, con apoyo de la reina María de las Mercedes, esposa de Alfonso XII, solicitó al Arzobispo de Toledo permiso para la construcción de una nueva iglesia en sustitución de la primitiva de Santa María de la Almudena situada en la calle Mayor, cuyo derribo en 1870 provocó la creación de una junta para erigir el nuevo templo. En 1878, el arquitecto Francisco de Cubas -más tarde marqués de Cubas por título pontificio- recibió el encargo del proyecto para su construcción en un solar al sur de la Plaza de la Armería, donde Sachetti, constructor del Palacio Real, ya imaginase una gran catedral. En 1883, el Rey don Alfonso XII coloca la primera piedra del que había de ser además panteón de su difunta primera esposa.
La iglesia pasará a ser catedral en 1885, cuando una bula del papa León XII cree la diócesis de Madrid-Alcalá. Ello supuso que el marqués de Cubas modificase el proyecto inicial (ambos proyectos se pueden ver en el Museo de la Catedral); diseñando entonces un grandioso templo de estilo neogótico francés, con planta en cruz latina de tres naves con capillas laterales conectadas entre sí; transepto también de tres naves y cabecera semicircular con girola y cinco capillas radiales. La imagen de la Virgen de la Almudena presidiría el Altar Mayor. La fachada principal, encarada al Palacio Real, tendría dos pares de torres de distinto tamaño flanqueando un gran pórtico de entrada con tres puertas de acceso, rosetón y galería de reyes. La cripta en estilo neorrománico, bajo la cabecera al sur, fue finalizada en 1911, después del fallecimiento del marqués en 1899, pero las obras avanzan lentamente y se suceden los arquitectos que van modificando el proyecto inicial, hasta cesar los trabajos en 1931 al anularse la consignación económica gubernamental para su prosecución.
Tras el obligado parón de la Guerra Civil (1936-1939), en 1944 se busca una nueva solución arquitectónica por concurso nacional, que es ganado por los arquitectos Fernando Chueca Goitia y Carlos Sidro, quienes proyectan un edificio para adecuarlo al entorno del Palacio Real, sobre todo, rebajando la altura del templo y dotándolo de un exterior clasicista más acorde con aquél. Las obras se iniciaron en 1950 por la zona próxima a la calle Bailén, realizándose el claustro, la fachada principal y completándose los primeros tramos de las naves. En 1960 se vuelven a paralizar las obras, siendo reanudadas en 1984 gracias al interés del Cardenal Suquía; creándose un Patronato para impulsar la construcción, que en lo esencial se concluye en 1993. La Catedral fue consagrada por el Papa Juan Pablo II el 15 de junio de ese mismo año, aunque las obras no terminaron totalmente hasta 1999, a falta de instalar algunos elementos decorativos. El interior de la Catedral presenta un estilo neogótico, con mobiliario procedentes de diversas iglesias y conventos, mientras que el exterior se encuentra en consonancia con el estilo del Palacio Real, como Sachetti lo había imaginado.