Kilise "Tanrı'nın En Kutsal Annesinin Doğuşu"

Vardar ve nehrin sol yakasında ve Serava nehrin sol yakasında Payko Maalo'daki (Ehit Paşa maalo), Üsküp şehrinin koruyucusu olan Tanrı'nın Kutsal Annesine adanmış en güzel ve en büyük katedral kilisesi bulunuyormuş. Kilise, Tanrı'nın En Kutsal Annesinin Doğuşu, Tanrı'nın Kutsal Annesi ve Tanrı'nın En Kutsal Annesi olarak bilinir.
"Tanrı'nın Kutsal Annesi" kilisesinin inşası, 1204'te Makedon ortaçağ kralı Dobromir Hrs tarafından başlatılmış ve oğlu Strez tarafından 1214'te tamamlanmıştır. Bu kilise, Türkler tarafından yıkıldığı 1688 yılına kadar varmış. Uzun yıllar sonra, 19. yüzyılın başında kilisenin inşası yeniden başlamıştır. Üsküp tüccarı Haci Kosta'ya göre, ustalar ve ağaç oymacılar 1809'da çalışmaya başlamışlar. Vasil Kunçov'a göre, 10 yıl bekledikten sonra, bina izni Sultan tarafından 1834 yılında İstanbul'da onaylanmıştır. İnşaattaki en büyük pay Üsküp birinci tüccar Aci Trayko Doyçinoviç tarafından verilmiş ve bu şahıs bu amaçla Üsküp metropoliti Gavril'i ve Üsküp Türk saygıdeğer Avzi Paşa'yı kendi tarafına çekmiştir.

Vardar yakınlarındaki bir çayırda kilisenin inşasıyla ilgili olarak, Üsküp'ün eski vatandaşları uzun süre bir fıkra anlatıyorşarmış. Kural olarak, kutsal yerlerde kutsal binalar inşa ediliyor ve Aci Trayko, buranın kutsal olduğunu kanıtlamak için, bir delikteki birkaç ortak ile birlikte Aziz Spas kiliseden ödünç alan birkaç eski tuğla ve Tanrı'nın Kutsal Annesi'nin küçük bir ikonunu gömmüş. Alana giden Türk komisyonu, kalıntı bulup yeri onayşamıştır. Aci Trayko şahsen Sultan Fermanı için İstanbul'a gitmiştir.
Kilise tüm Hristiyanların fonlarıyla inşa edilmiştir. Kilisenin inşatçısı Veles'ten Zografski soyundan Damyan Jankulov'muş, inşaat sırasında ölmüş ve tapınak oğulları tarafından tamamlanmıştır. Kilise 1 Mayıs 1835'te tamamlanmış ve kutlanmış ve iç tasarım daha sonra gerçekleştirilmiştir. Petre Filipoviç-Garka, Dimitar Stanişev ve diğerlerinin odun oymacılarının çalışması olarak, 1838'den 1842'ye kadar, alt kısmı mermerden üst kısımları  güncel heybetli oymayla ahşabtan yapılmış ikonostaz yapılmıştır. Piskoposun bulunduğu piskoposluk binası 1835 ve 1848'de inşa edilmiştir. Kilise bahçesine iki katlı bir okul dikilmiştir. 1875'te Sırp beyliği kiliseye küçük bir çan kulesi bağışlamıştır. Türk hükümeti tarafından zil çalınması yasağı nedeniyle kilise, çan kulesinin inşa edildiği 1909 yılına tahta kullanmıştır.
Birkaç yazarın ayrıntılı açıklamaları, kilisenin genişletilmiş batı kısmı olan bir revağı olan üç kısımlı bir bazilika olduğunu göstermektedir. Revağın birinci katında iki şapelli bir kadın kilisesi varmış. 1944'te II. Dünya Savaşı'nın sonlarına doğru, paha biçilmez zengin ikonostaz ve freskleri ile kilise Bulgar Faşist Ordusu tarafından ateşe verilmiştir. Savaş sonrası SFR Yugoslavya kapsamındaki SC Makedonya'daki yetkililer, tapınağı yenilememiş, bu yüzden 1963 depreminde tamamen yıkılmıştır. Kilisenin yeniden inşası 2005 yılında başladı ve 31 Ocak 2008'de kutsandı. Kilise, II.Dünya Savaşı'ndan önce olduğu gibi aynı görünüm ve mimariyle restore edilmiştir.