Aziz Nicholaos öldüğünde yapılan kilise veya şapel 529 yılındaki zelzelede yıkılınca daha büyük belki de bazilika tipinde bir kilise yapılmıştır.Bu kilise VIII. yüzyılda zelzele veya Arap akınlarıyla yıkılmış, daha sonra tekrar yenilenmiştir. 1034 yılında Arap donanmasının denizden yaptığı akınlarla harap olmuştur. On yıl harap durumda kalan kilisenin 1042'de Bizans İmparatoru IX. Konstantin Monomakhos ve eşi Zöe tarafından tamir ettirildiği kitabesinden anlaşılmaktadır.

XIII. yüzyılda Türklerin eline geçen Myra'da, kiliseyi serbestçe ibadet etmek için kullandığını ve kilisede bazı onarımların yapıldığını anlıyoruz.1853 yılında Kırım Harbi sırasında Ruslar kilise ile ilgilenmişler ve burada bir Rus kolonisi kurmak için Anna Golicia adındaki Rus kontesi adına toprak almışlardır. Ancak Osmanlı Devleti işin siyasî yönünü farkedince Rusların aldıkları toprakları geri almış, yalnızca kilisenin onarım istekleri kabul edilmiştir. Böylece 1862 yılında August Salzmann adında bir Fransız, Nicholaos Kilisesi'nin onarımı ile vazifelendirilmiştir. Bu restorasyonlar kilisenin aslını bozacak kadar kötü yapılmıştır. Bu restorasyon sırasında 1876'da bugün görülen çan kulesi de ilave edilmiştir.

Müze girişinden sonra taş döşeli yoldan aşağıya doğru inilir. İnerken Noel Baba'nın heykeli solda yeşillikler içinde görülür. IV. yüzyılda burada bulunan tek kubbeli kilisenin güneyine VIII. yüzyılda haç şeklinde bir şapel ile kuzey tarafına da eklemeler yapılmıştır.1862-1863 senelerinde de binaya dış narteks ile iç narteksin bazı kısımları ilave edilmiştir.

Bugün iki sütunu ayakta kalmış bir avludan bir iki basamakla Bizans Devri'nde ilave edilmiş güney nefine inilir. Haç biçimli bu bölümün doğu kısmında üç kemerli pencereye sahip bir apsis yer alır. Apsisin önünde orijinal stylobat ile ortasında altar kaidesi hâlâ görülür. Apsis nişinin içinde yer yer renkleri kaybolmuş ve belirsizleşmiş aziz figürleri vardır. Bunların altındaki küçük niş içindeki fresko Noel Baba'ya aittir. Bu bölüm ve esas kilisenin güneydoğu şapelinin tabanlarında farklı desenlerde mozaik panolar görülür. Batı yönünde merdivenlerin karşısındaki niş içerisinde İsa, Meryem ve Yahya freskoları vardır.

Buradan iyi muhafaza edilmiş kapı çerçevesi bizi lahitlerin bulunduğu kısma, yani haç biçimli şapelin uzun kısmına çıkartır. Lahitlerin yer aldığı nişler içindeki freskolar bugün net olarak görülmese bile çeşitli aziz tasvirlerini içeren freskolar ile bezenmiştir. Kuzey duvarındaki ilk nişle sütunların üzerinde Meryem freskosu ilginç örneklerdir. Noel baba freskosunun bulunduğu ikinci niş sütununun ters konduğu yazılarından anlaşılmaktadır.

Nişler içinde yer alan lahitlerden birinci niş içindeki akarthus yaprakları ile süslü Roma Devri lahdinin Noel Baba'ya ait olduğu kabul edilir. Hatta Noel Baba'nın denizcilerin de azizi olmasından dolayı lahdin üzerinin balık pulu desenleriyle süslendiği söylenir. 20 Nisan 1087'de Bari'li korsanlar, Noel Baba'nın kemiklerini almak için lahdi kırmışlar, bazı kemikleri alarak Bari'ye götürmüşlerdir.

İkinci niş ile karşısındaki nişte bulunan lahitler sadedir. Burada nişler içindeki lahitlerden başka yerde iki mezar daha bulunmaktadır. Buradan bir kapı ile kilisenin iri blok levhalarla döşeli avlusuna geçilir. Avluda ise bir niş içerisinde boşaltılmış iki mezar bulunur. Yanında bulunan mermer üzerinde haç ve çapa motifi Noel Baba için yapılmış olmalıdır. Solda duvar içine yerleştirilmiş mezardaki kitabede 1118 tarihi yer alır. Avludan önce dış nartekse, sonra üç kapı ile ana mekâna (naos) açılan iç nartekse geçilir. Burası gruplar halinde piskoposların resmedildiği freskolarla süslenmiştir. Buradan geçilen esas mekân üç kemerle yan neflere açılır. Ana mekânın güneyinde iki nef vardır.

İkinci nefte niş içindeki lahitte Noel Baba'nın mezarı olduğu söylenir ise de üzerindeki kadın erkek kabartması bunun böyle olmadığını gösterir. Yan nefin karşısındaki niş içerisinde ise birbaşka mezar vardır. Kuzey nefin kubbesinde Hz. İsa ve 12 havarinin freskoları bulunur. Yanda ise yan nefin kazısı yapılmaktadır. Bu kazının yapıldığı nefin batı kısmında ise üç oda bulunur. Binanın ortasında pencereli ve kasnaklı bir kubbenin olması gerekirken, Salzmann yaptığı tamir sırasında mekânın üstünü kapatarak, kesme taştan kaburgalı büyük bir çapraz tonoz kullanmıştır.