В первой половине XIX века на восточной окраине Тюмени простирался большой массив деревянной застройки, заканчивавшийся городским кладбищем. Здесь на месте старой деревянной церкви, построенной в 1779 году, по инициативе титулярного советника Дмитрия Войнова был заложен каменный храм. Освящение церкви состоялось в 1838 году. Внутреннее благолепие церкви создавалось трудами сына храмоздателя, коллежского советника Матвея Войнова.
С 1839 года церковь была приписана к Тюменской Покровской (Ильинской) церкви. Причта по штату не полагалось, кроме старосты, ухаживающего за церковью. Богослужения проводились редко. В 1884 году кладбище, где находилась Всехсвятская церковь, было закрыто, захоронение запрещено. Оно долгое время оставалось без хозяина и служило объектом расхищения. Относительный порядок был наведен лишь в 1908 году.
В первые годы советской власти, с обнародованием декрета 1918 года "Об отделении Церкви от государства и школы от Церкви", храм Всех Святых, как и другие культовые учреждения, в обязательном порядке должен был зарегистрироваться в качестве религиозной общины. И только 10 апреля 1923 года Всехсвятская религиозная община была зарегистрирована. В период антирелигиозных гонений церковь не избежала изъятия церковного имущества: из нее было вывезено более 12 кг серебряной утвари и два колокола весом 96 кг, находившихся у входа в храм.
В 1930 году все культовые здания Тюмени, за исключением Всехсвятской церкви, были закрыты. Судьба Всехсвятского храма тоже была предопределена: его собирались отдать под школу. Но планам этим не суждено было сбыться, и церковь продолжала действовать. В течение многих лет храм Всех Святых оставался в городе Тюмени единственным открытым местом общей молитвы.
При советской власти первым церковным старостой был избран Андрей Григорьевич Бояринцев. Во главе Церковного совета стоял протоиерей Николай Протопопов, являвшийся в то время настоятелем Ильинской церкви. С 1933 по 1937 год религиозную общину Всехсвятской церкви возглавлял Михаил Яковлевич Ханжин. Священником храма в этот период был о. Диоскор Татищев. Оба были осуждены "тройкой" Омского областного управления НКВД и расстреляны.
В годы "ежовщины" Всехсвятская церковь испытала на себе давление обновленцев, в связи с агрессивной деятельностью которых храм был закрыт с 1940 по октябрь 1941 года. Внешне он почти не пострадал, за исключением того, что с него сняли крест. В начале 1942 года власти дали разрешение на проведение богослужений. Крест изготовили на заводе «Механик» и установили на праздник Крещения Господня. Тогда же в храме был установлен иконостас, привезенный из разрушенной церкви села Заводоуспенка. Все средства, собираемые в храме во время Великой Отечественной войны, распределялись следующим образом: для фронта, для обновления храма, на общую свечу и на восстановление Знаменского кафедрального собора.
Первым организатором восстановления храма Всех Святых был священник Александр Сычугов. Впоследствии он был настоятелем храма, имел церковные награды. В эти же годы в храме служили священники отец Никифор и игумен Игнатий. Все они прошли ссылку и каторгу и были освобождены в 1942 году. В 1942 - 1950-х годах в храме Всех Святых служил священник Матфей Пахомов.
В 1980-е годы Всехсвятская церковь работала ежедневно, кроме понедельника и вторника. Ее посещали ежедневно 15-20 верующих, а в праздники до 500 человек.
В рамках подготовки к празднованию тысячелетия Крещения Руси в храме производились ремонтные работы. Инициатива реставрации и составления проекта принадлежала игумену Евтихию (Курочкину), брату тогдашнего настоятеля храма. Был установлен новый иконостас из резного дерева с позолотой, изготовленный в Омске, а демонтированный перевезли в Абалакский мужской монастырь. Кроме того, была произведена замена крыши храма. На куполе были установлены барабан, маковка и новый деревянный крест, обтянутый медью, который был впоследствии позолочен.
В 1997 году в храме было выделено дополнительное помещение и открыта детская воскресная школа и библиотека. В 1998 году начинал действовать детский хор. В этом же году впервые в Тюмени накануне праздника Рождества Христова на территории храма был сооружен Рождественский вертеп. В 2000-х годах в новосооруженном здании колокольни начал свою работу Молодежный центр.
Храм построен по плану архитектора Парамона. Уникальность постройки состоит в том, что это единственное в Сибири круглое церковное здание с перекрытым сводчатым куполом. Внешне церковь представляет собой одноэтажное здание-ротонду, к которому крестообразно примыкают четыре двухколонных портика.
В 1980-х годах был построен вместо деревянного большой каменный пристрой, где выделена комната под крестильню, где предусматривалась первая в Тюмени купель для полного погружения при совершении Таинства Крещения. Здесь же было отведено место для продажи свечей, церковной утвари и литературы. Строительство шло с большим трудом. Только в 2002 году Отдел по охране памятников культуры при администрации Тюменской области выдал официальное заключение о том, что пристроенная часть соответствует стилю храмового классицизма. Одновременно с пристроем были построены просфорня, ризная и прачечная. В 2004 году было завершено строительство отдельного здания колокольни.
1934-35 - 317 человек в общине
1936 - 344 человек в общине
1937 - 634 человека в общине
1979 - несмотря на то, что храм работал только по праздникам и воскресным дням, причтом Всехсвятской церкви было исполнено треб: крещений - 141, отпеваний заочных - 249, отпеваний в храме - 4, отпеваний на дому - 21
1980-е - храм посещали ежедневно 15-20 верующих, а в праздники до 500 человек
до 1933 года - см. список настоятелей Тюменской Ильинской церкви
Диоскор Татищев (1933 - 1937)
Игнатий (конец 1930-х?) игум.
Александр Сычугов (сер. 1940-х - 1954?)
Трофим Гончаров (1954)
Иоанн Шиприкевич (1954 - 1958)
Александр Кузнецов (1956 - 1957)
Александр Зелинский (1958 - 1967)
Иулиан Елисеев (1968)
Иаков Трофимюк (1968 - 1977)
Иоанн Петюк (1977 - 1982)
Иосиф (1983) свящ.
Михаил Курочкин (1983 - 1988)
Николай Морозов (1988 - 1989)
Гедеон (Харон) (1989 - 1991)
Владимир Клюев (1992 - 1997)
Андрей Сбитнев (с 1997)