Пантелеймоновская церковь в селе Балыктуюль построена в 1899 году усердием местных учителей (их имена не сохранились). По рассказам старожилов, основная финансовая помощь была оказана зайсаном Семеном Юлуковым (его усадьба была в местечке Ан Чеден. По информации старожила Кеденовой Ф., у зайсана был деревянный двухэтажный дом на левом берегу Балыктуюли, и он, кроме домашнего скота, разводил в загоне диких оленей, в клетках содержал лисиц. Имел много жен, но детей у него не было). По другим данным, зайсан выделил деньги на новое деревянное здание православной церкви, строительство которой было закончено в 1908 году. Строительством церкви руководил житель Чулышмана Тринихин. Церковь была освящена 24 июля 1899 года епископом Бийским. При храме имелся дом для священника и другие хозяйственные постройки. 14 марта 1905 года Указом Священного Синода в селе был открыт миссионерский стан, в том же году была открыта миссионерская школа и приют для детей. Дети обучались грамоте, ремеслу, церковному пению, получали медицинскую помощь.
Настоятелем храма в то время был священник Владимир Тозыяков. Одной из главных святынь храма до революции была икона Святого Великомученника и целителя Пантелеимона, привезенная из святой горы Афон (Греция). Икона была чудотворная, мироточивая, и очень почитаемая местными жителями, которые с верой помазывались миром, истекающим из иконы и получали исцеление. Очевидец Тузина А. Ф., умершая в 1991 году в возрасте 92 лет рассказывала: "Во время празднования храмового праздника занесли в церковь лежащего без памяти больного. После молебна, после того, как над больным пронесли икону Святого Великомученника и Целителя Пантелеимона, больной открыл глаза и самостоятельно поднялся на ноги". Таких случаев, по уверениям старожилов, было немало.
В 1929 - 1939 г.г. во времена гонения на церковь, храм был закрыт и частично разрушен, купола были заменены обычной крышей. В 1957 - 58 годах он был преобразован под клуб, в 1968 году его превратили в складское помещение для зерна, а с 1980 до 1993 года в помещении был краеведческий музей трудовой и боевой славы совхоза "Советский Алтай".
С апреля 1993 года в селе была организована приходская община, которая обратилась к администрации совхоза с просьбой вернуть верующим здание храма (многие годы верующие ездили креститься и праздновать великие праздники в г. Бийск). 21 июля 1993 года община была зарегистрирована. Начались работы по восстановлению храма под руководством настоятеля иеромонаха Макария (в миру - Илья Сергеевич Чулунов), который родился и вырос в селе Балыктуюль, а 30 июля 1993 г. был назначен настоятелем Пантелеймоновской церкви. С 7 августа 1993 г., спустя 63 года после закрытия и разрушения, в Пантелеймоновской церкви стали совершаться богослужения. Храм восстанавливался общими усилиями жителей всего Улаганского района во главе с Куюковой И. С. Руководил строительством церкви Кулешов Виктор Семенович, житель Турочакского района, он же главный оформитель и архитектор. Иконы (весь иконостас, «Распятие с предстоящими», многие другие иконы) написала член Союза художников России и Украины Махринская Галина Павловна. В восстановлении храма приняли участи многие жители села Балыктуюль: Бачишев В. Г., Чулунов Г. С., Штанов А.Н., Натов Т.П., Машкаков П.М., Тузин И.М., Гилев А.Н.
В апреле 1997 г. храм с Божьей помощью был завершен и украшен прекрасной орнаментацией.
6 августа 1997 года храм Святого Великомученника Пантелиимона был освящен Преосвященным Антонием, Епископом Барнаульским и Алтайским.
В августе 2005 года здание церкви (предположительно - в результате поджога) сгорело. Из икон удалось спасти всего несколько: Распятие с предстоящими, Николая-Угодника, Пантелиимона. Прихожане очистили пепелище, возвели новый фундамент, и новое строительство началось весной 2006 года. Уже осенью церковь открыла свои двери для верующих.
При храме открыта воскресная школа, где дети обучаются Закону Божьему, церковному песнопению и получают первичное музыкальное образование. В Рождество и Пасхальные праздники учащиеся Воскресной школы показывают прихожанам праздничные концерты и представления. Занятия с детьми ведут учителя Чулунова А. С., Гузина Т. И., Кокпашева И. Ф.
Верующие со всего района приезжают в церковь на церковные праздники. Богослужения проводятся на двух языках: церковнославянском и на алтайском.
В августе 2010 года на храмовом празднике в церкви присутствовали многочисленные паломники из Горного Алтая, иереи, епископ Барнаульский и Алтайский Максим.
В начало