Идея возведения церкви принадлежит Александру Гавриловичу Журуну, который в 1975 году привёз из села Скородум Упоровского района старинную икону, доставшуюся ему от бабушки. Долгое время изображение на иконе было неразличимо, однако спустя 15 лет оно начало обновляться, и стало ясно, что на ней изображён святитель Николай Чудотворец. Вдохновлённый этим событием, Журун передал икону в часовню посёлка Мыс и начал работу над проектом строительства храма в честь святителя Николая.
В марте-апреле 2004 года было собрано около трёх тысяч подписей жителей Восточного микрорайона с просьбой о предоставлении участка под строительство церкви. 31 мая 2004 года состоялось освящение места и установка поклонного креста, ознаменовавшие начало реализации проекта. Для организации строительства 11 февраля 2005 года была зарегистрирована местная православная религиозная организация «Приход Святителя Николая, Архиепископа Мир Ликийских, Чудотворца».
25 марта 2005 года был создан попечительский совет по организации строительства храма, возглавляемый председателем Тюменской городской Думы Сергеем Михайловичем Медведевым. В начале 2006 года удалось оформить документы на землю и разработать проектно-сметную документацию. Проект храма был выполнен коллективом «Сибспецпроектреставрация» под руководством генерального директора и главного архитектора проекта В.А. Силантьева.
28 июля 2006 года наместник Тюменского Свято-Троицкого монастыря архимандрит Тихон (Бобов) совершил чин освящения места под строительство храма. В основание были заложены освящённые камни, привезённые из Ганиной Ямы — места убиения царской семьи, а также горсть песка из древнего города Миры, где святитель Николай служил архиепископом.
Строительство храма велось при активном участии генерального подрядчика — предприятия ОАО «Промжелдортранс-Тюмень» под руководством генерального директора В.П. Саломатина. Работы по возведению стен, куполов и кровли были завершены к 2008 году. 27 июля 2008 года, в день празднования 422-летия города Тюмени и 1020-летия Крещения Руси, в новопостроенном храме был отслужен первый водосвятный молебен и освящён иконостас.
Архитектурно храм представляет собой кирпичное здание на цокольном этаже. Он выполнен в традиционном русском стиле: бесстолпный одноапсидный четверик, завершённый луковичной главкой на горке кокошников, с притвором, шатровой колокольней и крыльцом на два всхода с южной стороны.
Внутреннее убранство храма включает пятиярусный деревянный иконостас, изготовленный мастерской А.Ф. Квасневского. Все пятьдесят пять икон иконостаса были написаны самим мастером. Ростовые иконы святителя Николая и Валаамской Божией Матери выполнены художником Николаем Ивановичем Сидоровым.
При храме организованы различные общественные и образовательные структуры: воскресная школа «Божья коровка», детская дружина имени Евгения Родионова, общество трезвости «Бодрствование», сестричество и социальная служба. Эти подразделения способствуют духовному просвещению и социальной поддержке прихожан и жителей микрорайона.
