Приход Русской Православной Церкви в Мадриде существует с 1761 года, с  момента, когда в Мадриде указом императрицы Екатерины II была учреждена посольская церковь, в которую морем были направлены причт и необходимая утварь. Наибольший вклад в дело процветания посольского храма св. равноапостольной Марии Магдалины внес священник Константин Кустодиев, служивший в нём с 1865 по 1870 гг. Богослужения в церкви совершались вплоть до ее упразднения в 1871 году, когда иконостас и утварь из нее были перевезены в Буэнос-Айрес (Аргентина).

С закрытием храма святой равноапостольной Марии Магдалины регулярные православные богослужения в Мадриде прекратились и были возобновлены только после окончания Второй мировой войны.

Храм святой мученицы царицы Александры, существовавший в послевоенную эпоху, располагался в арендованных помещениях.

Богослужения Христорождественского прихода, учрежденного в 2001 году, совершались поначалу дома у первого настоятеля иеромонаха Арсения (Соколова), затем в бывших магазинах, переговорных пунктах и мастерских.

В январе 2004 года на приход прибыл новый настоятель о. Андрей Кордочкин, который с первых же дней после своего приезда в Мадрид взял под свою духовную опёку молодой приход. При его непосредственном участии мадридский Христорождественский приход смог осуществить свою многолетнюю мечту: иметь свой храм на испанской земле.

9 июля 2010 г. в мэрии Мадрида было подписано соглашение о выделении городскими властями участка земли Русской Православной Церкви для строительства храма. Подписание договора о передаче земли для строительства стало плодом многолетних усилий Посольства РФ в Мадриде и лично Посла — Александра Игоревича Кузнецова.

5 октября 2011 г. было получено разрешение на строительство. 6 декабря 2011 г. архиепископом Егорьевским Марком и епископом Корсунским Нестором был освящен закладной камень будущего храма.

Само строительство было начато через несколько дней после церемонии. В состав Попечительского совета, вместе с архиепископом Егорьевским Марком — секретарем Московской Патриархии по зарубежным учреждениям, вошла Государыня Великая Княгиня Мария Владимировна Романова, которая живет в Мадриде.

Строительство стало возможным благодаря поддержке благотворительного фонда «Транссоюз», испанской вагонностроительной компании «Тальго» и многих других, кто принес малую жертву от своих трудов.

Первое богослужение было совершено в Великий Четверток 2 мая 2013 года.

Каменный иконостас был установлен в 2015 году.

18 января 2019 года храму святой равноапостольной Марии Магдалины был присвоен статус Кафедрального собора епархии.

В начале 2022 году начались работы по росписи стен фресками, которые завершились в конце 2023 года.

Состав прихожан многонационален. Есть среди них русские, украинцы, молдаване, армяне, грузины, болгары, испанцы, а также представители Северной и Южной Америки.

Храмовый образ святой равноапостольной Марии Магдалины заслуживает особого рассказа. Он пребывал в домовой церкви в честь святой, которая был устроена при российском посольстве в Мадриде в XVIII-XIX вв. Нам удалось найти икону на родине Че Гевары, в аргентинском городе Росарио. По доброй воле митрополита Буэнос-Айресского и Аргентинского Силуана (Антиохийский Патриархат), икона вернулась в Мадрид спустя 120 лет пребывания за океаном.
Киот для иконы изготовил в Великобритании Эйдан Харт, его же руками сделан киот для Иверской иконы Пресвятой Богородице в монастыре Ивирон на святой горе Афон. Он же изготовил врата для нашего храма, украшенные иконами в технике огневого золочения.

В нашем храме пребывают святыни — частицы мощей святых: св. равноапостолной Марии Магдалины, святой равноапостольной царицы Елены, святителя Иннокетия Иркутского, преподобного Серафима Саровского, благоверных князей Петра и Февронии Муромских, преподобных Иова и Амфилохия Почаевских, священномученика Владимира Киевского, а также древних испанских святых — мучениц Евлалии Меридской и Леокадии Толедской, а также преподобного Эмилиана отшельника.

Мы дорожим нашей связью древней христианской Испанией. Несколько раз в интерьере храма повторяется форма древнего астурийского «креста ангелов» , изготовленного в VII-IX вв, а светильники, выполненные в московской мастерской Кавида, выполнены в форме одной из вестготских корон VII-ого века, которые вешались в алтаре над престолом (см. изображение в нижнем правом углу).

В апреле 2015 года, накануне Великого освящения нашего храма, в алтаре были установлены мраморный престол и жертвенник. Их проектированием занимались настоятель храма прот. Андрей Кордочкин и английский скульптор и иконописец Эйдан Харт. Престол и жертвенник были изготовлены в Мурсии скульптором Антонио Солером.

Мы попытались создать такое алтарное пространство, которое выражало бы православную традицию, и в то же время было связано с искусством древней Испании.