Первое упоминание о церкви Спаса Нерукотворного города Тюмени относится к первой четверти XVII века. В 1687 году первый деревянный храм был уничтожен пожаром, после чего он был отстроен и вновь неоднократно уничтожался огнём на протяжении XVII и XVIII веков. Из-за столь частых пожаров встал вопрос о строительстве каменной церкви.
По благословению архиепископа Тобольского и Сибирского Варлаама I (Петрова), двухэтажная каменная церковь была заложена в 1794 году. В 1797 году храм нижнего этажа был освящён в честь Тихвинской иконы Божией Матери.
Строительство верхней церкви растянулось на долгие годы и завершилось лишь в 1819 году с освящением в честь Нерукотворного Образа Христа Спасителя. Престол в честь Спаса Нерукотворного считался главным. По нему церковь и стала именоваться Спасской, так же как и проходящая мимо церкви улица (ныне ул. Ленина).
В 1837 году церковь посетил цесаревич Александр, будущий император Александр II вместе со своим воспитателем - поэтом Василием Жуковским.
В приход входили деревни Комарова, Падерина и Копытова. В деревне Падериной имелись приписной к Спасской церкви храм, освященный в 1908 году, и смешанная церковно-приходская школа (с 1909 года). В 1914 году по желанию и на средства старосты церкви купца А. И. Текутьева было начато строительство северного придельного храма, в котором размещались два престола: на первом этаже - во имя преподобного Андрея Критского и преподобномученицы Евдокии, на втором - во имя святителя Иоанна Тобольского и преподобного Сергия Радонежского. Строительство завершилось в 1916 году - в год смерти Текутьева. Позднее западные фасады основного и придельного храмов были объединены пристроенной к ним двухэтажной папертью-притвором в псевдорусском стиле. При церкви также находилась разобранная в 1930-х годах отдельно стоящая колокольня.
В годы советской власти:
В начале 1920-х годов, в ходе кампании по изъятию церковных ценностей, из Спасской церкви было изъято 4 пуда и 6 фунтов серебра.
В июне 1927 года в Тюменский окружной комитет партии поступила жалоба от церковного совета Спасской церкви тихоновского течения. В ней указывалось:
"Церковь, где мы ютимся, не может вместить всех прихожан, а их насчитывается около 1500 человек. Однако Знаменская и Михайло-Архангельская церкви отданы обновленцам во главе с протоиереем В. Марсовым, численность которых не более 160 человек. Мы обращаемся к Вам с просьбой о передаче нам Знаменского собора". Ходатайство было отклонено.
В декабре 1929 года церковь была закрыта "за неуплату долгов и за невыполнение обязательств" по использованию культового имущества.
17 апреля 1930 года верующие попытались возвратить её в свое пользование. Они обратились в горсовет, однако прошение было отклонено "ввиду того, что церковь закрыта на основании требования рабочих масс и уголовного преступления служителей церкви". "Уголовное преступление служителей церкви" было описано в статье под заглавием "Схимники спасские, или Ночные похождения двух старцев" газеты "Красное Знамя" за 31 декабря 1929 года. В ней утверждалось, что 17 декабря 1929 года под покровом ночи священники Илия Популов и Алексий Тоболкин сорвали печать адмотдела и, проникнув внутрь помещения церкви, похитили девять икон, огромное количество свечей, пять кусков красного шелка и множество других вещей.
С 1930 года здание церкви стало использоваться в качестве общежития. Здание находилось под охраной Наркомпроса, и благодаря этому не было уничтожено.
В 1945 году верующие города обратились к местным властям с просьбой об открытии в городе второй церкви (единственным действующим храмом оставался кладбищенский Всехсвятский). Внешний вид здания полностью сохранился и ему требовался лишь текущий ремонт. Кроме того, здесь сохранился иконостас. Тюменский горсовет, учитывая расположенность по соседству со зданием просимой церкви двух школ, детского садика и городского общественного сада имени В. И. Ленина, не желая создавать "нездорового контраста", отказал в передаче храма.
В 1950 году в здании разместилась Тюменская областная библиотека. 30 августа 1960 года здание было взято под государственную охрану как памятник архитектуры республиканского значения и включено в реестр монументального зодчества местного значения. В 1982 году здесь разместились фонды и научная библиотека Областного краеведческого музея.
Новейшая история:
15 июля 1991 года Президиум Тюменского городского совета народных депутатов принял решение о передаче здания храма Тобольско-Тюменской епархии. Областной краеведческий музей не выполнил принятого решения, и на 2013 год здание не передано под юрисдикцию Русской Православной Церкви.
24 марта 2002 года при Спасской церкви был создан приход, окормляемый духовенством Знаменского кафедрального собора. Прихожане регулярно совершают у стен храма чтение акафистов.
К 2005 году фасад храма был отреставрирован, поставлен купол.
В 2004-2005 годах при проведении земельных работ, связанных с реставрацией и укреплением фундамента здания церкви, на территории, прилегающей к храму, были обнаружены человеческие останки. Их погребение было совершено 30 ноября 2008 года в братской могиле в восточной части храмовой территории.
