Первая церковь в Улале была построена в 1838 году. В ней находился походный антиминс во имя Всемилостивого Спаса. В 1873 году храм горел, и в 1873-1874 гг. было построено новое здание на средства Православного Миссионерского общества на пожертвования Высокопреосвященного Иннокентия (Вениаминова), Митрополита Московского и других Благотворителей миссии.
Символично, что храм был построен на месте, где жил первый крещеный основателем Алтайской духовной миссии алтаец – Элеска – Иоанн.Он рано умер, а дети его стали жить самостоятельно. К ним переселился тесть Иоанна-Элески, крестьянин Евфимий, и таким образом дом оказался пустующим и весьма ветхим. Тогда было решено на этом месте строить храм. Евфимий умер в возрасте 110 лет незадолго до окончания строительства храма.
Ограниченность в средствах, отсутствие местных техников архитекторов вынудили начальника миссии Архимандрита Владимира (Петрова) «сим делом заняться самому, пользуясь местными мастеровыми и руководя их лично»… Церковь выстроена применяясь к Высочайше утвержденному для сибирских церквей №5-му проекту, с нужными по местным причинам размерами». План был разработан самим начальником миссии Владимиром (Петровым).
Постройка этого благолепного храма окончилась в 1875 г. Параллельно его строительству были проведены работы по укреплению русел рек Маймы и Улалы.
Торжественное освящение нового храма Всемилостивого Спаса состоялось 21 сентября 1875 г. Возглавил богослужение по благословению правящего архиерея начальник Миссии архимандрит Владимир. Ему сослужили 12 священников и три диакона. Несмотря на слабую информированность, на освящение собралось около 3000 верующих.
С 1879 г. в этом храме находилась чудотворная икона великомученика и Целителя Пантелеимона с частицей мощей, присланная с Афона. Периметр лика украшали изображения из жизни святого. В 1880 г. на икону была сделана подобающая риза.
В непосредственной близости находился комплекс миссионерского стана со всеми необходимыми постройками – дома начальника Алтайской миссии с домовой церковью, Училищного дома, (впоследствии женской и мужской школы), детского приюта и миссионерской больницы. При церкви находится миссионерская церковная библиотека, в которой насчитывалось 685 наименований книг.
С установлением советской власти на церковь начались гонения. Храм был закрыт 14 февраля 1929 г., 15 июня того же года с него были сняты колокола и кресты. В 1930 г. здание было переоборудовано под кинотеатр.
8 августа 1932 г. было принято решение о сносе Спасского храма, которое так и не было претворено в жизнь. В 1942 г. здание храма стало столовой общепита «Алтайторга», а с 1943 г. помещение передали под столовую треста «Ойротзолоторедмет».
В середине XX в. храм был снесен.
В настоящее время на месте храма располагается Горно-Алтайский экономический техникум.
