Первый молитвенный дом в селе Бирюля был построен в 1859–1861 годах на средства К.Е. Параева. Новая церковь была возведена в 1884–1885 годах на пожертвования бийского купца Якова Ивановича Окулова, второго мужа вдовы Александра Боробоша. Освящение храма совершилось по благословению епископа Бийского Макария (Невского), а чин освящения провел помощник начальника Алтайской духовной миссии протоиерей Василий Вербицкий.
Здание храма представляло собой деревянную обшитую тёсом постройку с алтарной частью, увенчанной главкой, одноглавым основным объёмом, трапезной и притвором с одноярусной колокольней. После закрытия Улалинского монастыря в Бирюлинский храм была перенесена чудотворная икона Святителя Николая. В феврале 1930 года президиум облисполкома принял решение о закрытии уже не действующего храма. В советский период здание использовалось как клуб, магазин и склад, при этом были утрачены архитектурные завершения.
В начале 2000-х годов началось восстановление храма с отступлением от исторического проекта. 6 декабря 2014 года епископ Горноалтайский и Чемальский Каллистрат совершил чин великого освящения и Божественную литургию архиерейским чином. Храм был вновь освящен в честь великомученика Пантелеимона Целителя.