İ. S.5. Yüzyılda Myra’nın likya eyaletinin başkenti, Mira başpiskoposu’nun da Anadolu’nun ikinci büyük din otoritesi olmasi, Aziz Nikolaos’un ölümünden sonraki yıllarda şehrin saygınlığının artmasinda büyük rol oynamıştır. Myra halkı ölümünden sonra aziz adına önce bir anıt, sonra da büyük bir bazilika inşa ettirmiş, bu devirde aziz adına İstanbul’da da büyük bir kilise inşa edilmiştir. Myra’daki bazilika depremler ve şehre yapılan akınlar sonucu 8. Yüzyılda büyük hasar görmüş, 9. Yüzyılda ise kubbeli kilise olarak yeniden inşa edilmiştir. Daha sonraki ilaveler 11. Yüzyılda orta Bizans devrinde gerçekleşir. Bu dönemin en önemli onarımının 1042’de imparator IX. Konstantin ile karısı zoe tarafından yapıldığı bilinmektedir. Duvar freskleri ve taban mozaiklerinin çoğu bu döneme aittir. Yüzyıllar içinde çeşitli nedenlerle oldukça tahrip olmuş kilisenin diğer geniş kapsamlı onarımı 1853 yılında Rus çarı I. Nikolaos tarafından gerçekleştirilmiştir.
Orijinal planından oldukça sapmış bu onarıma ait çan kulesi ve omurgalı yeni orta kubbe bu çalışmaların ürünüdür. Aziz Nikolas kilisesi Bizans sanat tarihinin önemli bir anıtı, mimari süslemeleri ile orta Bizans döneminin seçkin bir örneğidir. Bugünkü kilisenin özgün temelleri üzerinde değişik zamanlarda yapılmış birçok yapı bulunur. Böylece kilise çeşitli dönemlerde inşa edilmiş bir kompleks görünümündedir. Bu kompleks ana hatlarıyla; avluya açılan iki narteks (iç avlu), iki yan koridorun arasında yer alan kubbeli bir orta mekânla (naos), bema ve önündeki syntranonlu (koro basamaklari) apsisten ibarettir. Diş narteks 1853 yılı onarımında yeniden inşa edilmiş, iç narteks ise çoğunluk özgün temeller üzerindedir. Tonozunda peygamber ve konsül toplantılarının resmedildiği, kilisenin en eski duvar freskleri bulunur.
Güney koridorun aziz’in lahdini korumak için en uygun yer olduğu düşünülmekte, doğu köşedeki nişin içinde ise aziz’in lahdinin korunduğuna inanılmaktadır. Ayrıca kuzey-doğu ve güney-bati köşelerde kubbeleri freskli iki oda yer alır. Bu yapı 8. Yüzyıla tarihlenmekte ancak ilk inşasının 5–6. Yüzyıllarda olduğu bilinmektedir.