В 1602 г. за пределами стен кремля была построена деревянная церковь во имя Николая Чудотворца. Храм был возведен за десять дней, по случаю явления Святителя Николы, чтобы прекратить в городе падеж скота.
Возле церкви находилось небольшое кладбище, на котором покоятся дети и внуки первых тоболяков и казаки Ермака.
В августе 1643 г. деревянная Никольская церковь сгорела, а затем была восстановлена. 29 мая 1677 г. храм погиб в пожаре, погубившем половину города. В следующем году был заложен новый деревянный храм св. Николая, епископа Мирликийского с приделом великомученика Димитрия Солунского. Новый храм был освящен 3 декабря 1680 года.
В 1684 г. в Никольскую церковь попала из тучи «громовая стрела» (метеорит), пробила верх большой главы и упала внутрь церкви, в придел. Камень долгое время находился в приделе Димитрия Солунского. Там же хранился интереснейший документ XVII в. «Синодик Ермаковским казакам» с поименным списком казаков, погибших во времена «сибирского взятия». Ежегодно 26 октября проводилась поминальная служба.
Кроме «громовой стрелы» и синодика в церкви находились две деревянных резных скульптуры св. Николая. Они пользовались в народе большим почитанием. По указу Тобольской духовной консистории от 30 сентября 1835 г. они были убраны из церкви и заменены обычными иконами.
В 1714 г. был заложен каменный храм с приделами Входа Господня в Иерусалим, великомучеников Димитрия Солунского и Георгия Победоносца.
По малочисленности прихожан служба в храме совершалась редко. Во второй половине XIX в. южная его стена дала значительную трещину. В 1891 г. преосвященный Иустин на добровольные пожертвования привел церковь хотя и не в роскошный, но в приличный вид.
30 мая 1901 г. в Никольской церкви крестили Бориса Павловича Грабовского.
По сведениям «Справочной книги Тобольской епархии» в 1908 г. в приходе Никольской церкви проживало 1697 человек.
В приходе значилось 14 деревень: Завальная, Защитина, Поварня, Козлова, Верхнефилатова, Зырянова, Саргина, Маркова, Волгина, Савина, Редькина, Кондрахина, Веснина и Самохвалова. В 1913 г. в них было 324 двора, проживало 1588 чел. (810 м., 778 ж.).
После революции, до начала двадцатых годов в церкви совершались богослужения, а затем ее превратили в гараж тюрьмы УГБ НКВД. Доведя до аварийного состояния, власти города в 1930 году закрыли храм. Затем он был полностью разрушен.
В старину в нагорную часть Тобольска вели Прямской и Казачьи взвозы. В 1824 г. был устроен более удобный и пологий Никольский взвоз, который был назван так по находящейся неподалеку Никольской церкви. Первоначально планировали укрепить стены Никольского взвоза кирпичом, но кирпича не хватило даже на мостовую, которая была деревянной.
Никольская церковь, венчающая взвоз, являлась третьей по времени постройки в Тобольске. Первый Никольский храм был построен в 1602 г. в течение 10 дней, по случаю явления Святителя Николы, чтобы прекратить в городе падеж скота.
Возле церкви находилось небольшое приходское кладбище, на котором покоились дети и внуки первых тоболяков. Здесь, а это можно утверждать с большой долей вероятности, покоятся казаки — участники похода Ермака и архитектор С. У. Ремезов.
Деревянная Никольская церковь несколько раз обновлялась. В 1684 г. в церковь попала из тучи «громовая стрела» (метеорит), пробила верх большой главы и упала внутрь церкви, в придел. Камень долгое время находился в приделе Димитрия Солунского, дальнейшая судьба метеорита неизвестна.
В 1743 г. был заложен каменный храм с приделами Входа Господня в Иерусалим, великомучеников Димитрия Солунского и Георгия Победоносца. Во второй половине XIX века южная стена храма дала значительную трещину. В конце XIX в. храм был отремонтирован.
30 мая 1901 года в Никольской церкви крестили Бориса Павловича Грабовского, ставшего изобретателем телевидения. По сведениям «Справочной книги Тобольской епархии», в 1908 году в приходе Никольской церкви проживало 1697 человек.
В 1930-х годах храм был разрушен. По воспоминаниям старожилов города, сначала в церкви размещались складские помещения, а затем гараж НКВД. Церковь простояла после этого недолго и рухнула. Кирпич и мусор на месте рухнувшей церкви оставался до весны 1941 года. Затем его убрали к Первомаю.
Летом 2012 года группа тобольских археологов под руководством Александра Адамова обнаружила точное местонахождение каменного храма середины XVIII века. В небольшом раскопе (около 30 кв. м) были обнаружены хорошо сохранившаяся алтарная часть Никольской церкви и массу захоронений вокруг и внутри нее. Значительная часть захоронений принадлежала деревянной Никольской церкви 1602 года.