התוכניות להקמת קתדרלה על שם הבתולה מאלמודנה עלו במהלך המאה ה-16 מהרגע בו הפכה מדריד לבירת ספרד על ידו של המלך פיליפ השני, אך בנייתה נדחתה לאורך זמן רב עקב התנגדותה של הבישופות של טולדו שפחדה מפגיעה במעמדה. כך שבניית הקתדרלה בפועל החלה רק במאה ה-19 (בשנת 1879). בנייתה של הקתדרלה התנהלה בעצלתיים ואף הופסקה כליל עם פרוץ מלחמת האזרחים הספרדית. עבודות הבנייה נמשכו בשנת 1950, והקדתרלה נפתחה רק בשנת 1993, יותר ממאה שנים לאחר תחילת העבודות, בנוכחות האפיפיוריוחנן פאולוס השני.
סגנון ועיצוב
תכנון הקתדרלה שהבנייה החלה על-פיו היה בסגנון התחייה הגותית, אך עם המשך עבודות הבנייה לאחר מלחמת האזרחים, הוחלט לעצב את חלקה החיצוני בסגנון נאו קלאסי, במטרה להתאים את הקתדרלה לחזיתו של הארמון המלכותי הניצב מולה. עיצוב פנים הקתדרלה נחשב לחדשני ומודרני, עם חדרי תפילה ופסלים של אמנים בני זמננו המעוצבים בסגנונות שונים.