Церковь Андрея Первозванного была построена в 1646 году по благословению Архиепископа Сибирского и Тобольского Герасима на южной окраине города в «казачьей» слободе. Ходатаями и строителями первого деревянного храма были тобольские казаки. Среди них – казак Тимофей Сыромятников, прибывший в Тобольск еще с дружиной Д. Чулкова.
Почти через 100 лет, в 1744 году на средства прихожан была заложена каменная Апостоло-Андреевская церковь, а в 1759 году было закончено ее строительство. В храме было три престола: во имя св. апостола Андрея Первозванного, во имя св. мученика Иоанна Воина, во имя преп. Амвросия Затворника. Колокольня храма из-за значительной высоты дала трещины. Поэтому ее в 1806 году перестроили.
На погосте этого храма были похоронены: купец Авраамий Сумкин (1748 г.); семейство Феодора Сыромятникова (1740-1788 гг.); священнослужители: о. Симеон (Васильев); о. Симеон (Лаврентьев); о. Иоанн (Данилов).
В 20-е годы ХХ века с храма были сняты кресты, церковное имущество было передано в государственную казну. В 1930 году церковь была закрыта. В храме располагались гаражи Окрпотребсоюза и контора треста общественного питания.
В 1999 году храм в аварийном состоянии передали Тобольско-Тюменской епархии. В настоящее время идет его реставрация.
Тобольско-Тюменская епархия http://www.tobolsk-eparhia.ru/p/blag/php/place.php?id=tob&id1=3&id2=1