W tym samym roku, przy południowej części fortu, staraniem wojewody A.S. Sinjawina, położono kamień węgielny pod budowę nowej, murowanej cerkwi, który poświęcił metropolita tobolski i syberyjski Filoteusz. Architektem świątyni był Mojżesz Iwanowicz Dolgich z Moskwy, który pracował wcześniej w Tobolsku, wznosząc m.in. cerkwie. Główny budynek został wybudowany w 1710, a dzwonnica i iglica pojawiły się później – w 1758. Najstarsza część świątyni ma kształt czworokątny.
Świątynia zawiera w sobie tradycje starych rosyjskich cerkwi podmiejskich, z dwukondygnacyjnym refektarzem z zachodu i okrągłą absydą od wschodu. W 1710 w tzw. zimnej kaplicy na pierwszym piętrze, poświęcono ołtarz Obrazu Zbawiciela Nie Ludzką Ręką Uczynionego, zaś w 1713 na parterze w tzw. ciepłej kaplicy – ołtarz św. Mikołaja Cudotwórcy. Tutaj także, na parterze, tak jak w niemal wszystkich starych rosyjskich cerkwiach, przechowywano pieniądze oraz inne cenne dla fortu przedmioty, m.in. ziarno.