Сведений о том, когда в Нарве началось строительство каменной церкви, не имеется, но известно, что в 1442 г. она уже строилась, а в 1467 г. городской магистрат обратился к Таллинну за помощью в сооружении крыши церкви. Строительство продолжалось и в начале XVI века. Так известно, что в 1519 г. возводились своды над алтарной частью. Церковь была зального типа, строительным материалом служил местный известняк. В плане здание имело размеры 20х47 м. Три одинаковых по ширине и высоте нефа перекрыты крестовыми сводами. С южной стороны стена подпиралась мощными пилонами — контрфорсами. Восьмигранные внутренние пилоны венчались простыми капителями. Четырехугольная в основании башня над коньком кровли переходила в круглую. Архитектура Нарвской церкви была схожа с рядом других сооружений Северной Эстонии и острова Сааремаа, в частности, с хорами Олайской церкви в Таллинне (пилоны, капители, своды). Предполагается, что церковь в Нарве строилась таллиннскими мастерами. В средние века в Нарвской церкви имелось несколько алтарей, которые были разгромлены во время реформации в 1532 г. Башня церкви неоднократно горела — в 1529, 1610, 1659 и 1782 гг., но каждый раз восстанавливалась. В последний раз она была восстановлена в 1842 г. В начале XVIII в. Нарвскую средневековую церковь, которая первоначально была католической, а затем лютеранской, освятили в православный Спасо-Преображенский собор.
Переоборудование в Нарве средневековой городской церкви в православный собор привело к созданию нового интерьера. Примечательным, и даже уникальным художественным произведением был иконостас нарвского Спасо-Преображенского собора. Иконостас состоял из трех частей — двух боковых и несколько заглубленной в сторону алтаря центральной части с царскими вратами. Северная боковая часть иконостаса располагалась до того в церкви Александра Невского, в которую в 1704 г. была переосвящена шведская домская церковь и представляла собой стену из икон в богатом обрамлении.