Судьба первой деревянной церкви неизвестна. Строительство второго деревянного храма начинается 14 января 1852 г., когда доверенный от общества крестьян Степан Никитич Чалдин подал прошение на имя Государя Императора Николая I на «…построение новой деревянной церкви, во имя святой Троицы, в означенной деревне Брюхановой». 5 июня 1852 г. состоялась закладка храма, возводившегося в течение трех лет на народные пожертвования. По окончании строительства еще целый год выполнялись живописные работы. Торжественное освящение уже завершенного храма во имя Святой Троицы произошло 26 ноября 1856 г. по благословению епископа Парфения. Архитектурный облик деревянной Троицкой церкви можно представить лишь по аналогам, сохранившимся в архивах в виде проектной документации. Вероятно, его образность строилась на сочетании приемов культовой традиционной архитектуры и классической стилистики. Так как типология церковных проектов не была чем-то застывшим и неизменным, она давала возможность архитекторам Томской Духовной Консистории и Губернского строительного комитета корректировать свои проекты сообразно местным условиям. Кроме того, осуществление проекта находилось в прямой зависимости от собранных по приходу средств.
В 1898 г. деревянная Троицкая церковь сгорела, но большую часть ценного церковного имущества и библиотеку удалось спасти. Богослужения временно проводились в молитвенном доме, выстроенном на месте сгоревшей церкви. Сбор средств на строительство нового храма решением схода жителей и с разрешения Томской Духовной семинарии проводился в течение года крестьянами сел Брюхановского и Дмитриевки А.П. Карнауховым и В.Ф. Радостаевым по всей епархии.
Большую роль в возведении нового каменного храма сыграл вступивший с 1902 г. в должность настоятеля священник Павел Иванович Кобылецкий. Получив образование в Томской Духовной Консистории, он был рукоположен в 1895 г., после чего состоял Змеигородским уездным наблюдателем церковных школ и следователем 29-го благочиния. Награждался бронзовой медалью за участие во всеобщей переписи населения Российской империи, а в 1901 г. — набедренником за усердную пастырскую службу. Сразу по прибытии на службу в село Брюхановское он написал рапорт в Томскую Духовную Консисторию о возведении каменного храма, в котором говорилось: «…с самого первого дня моего служения в селе Брюхановском я прилагаю все старания к тому, чтобы расположить прихожан к постройке храма, и, благодарение Господу Богу, прихожане 2 февраля 1903 г. постановили приговор о постройке в селе Брюхановском каменного храма, который бы мог вместить 500 молящихся; при этом прихожане проявили согласие внести в кассу попечительства на постройку вышеозначенного храма по 10 рублей с каждого лица мужского пола от 15 до 60- летнего возраста в продолжение четырех лет». В 1907 г. проектная документация каменной Брюхановской церкви была утверждена строительным отделением Томского губернского правления. Архитектором И.О. Носовичем был откорректирован один из типовых проектов Атласа чертежей Священного Синода, положенного за основу при возведении Брюхановского храма. Строительство намечалось на прежнем месте, в центре уже сформировавшейся к тому времени сельской площади. Поэтому молитвенный дом отсюда переносился на местное кладбище с сохранением за ним прежней служебной функции, но с изменением престола во имя прп. Серафима Саровского.
24 июня 1908 г. при большом стечении народа благочинный Леонтий Попов в сослужении священников других приходов совершил торжественное освящение закладного камня Троицкой каменной церкви. На старинной фотографии тех дней, хранящейся в сельском музее истории крестьянского быта, запечатлены благочинный Леонтий Попов, настоятель П.И. Кобылецкий, псаломщик А.Е. Зеленков, церковный староста С.Н. Пьянков, диакон Н.А. Наганов, председатель церковноприходского попечительства П.Е. Перевалов. Каменный храм возводится в исключительно короткие сроки, несмотря на его довольно внушительные размеры. Уже через год, 12 июня 1909 г., в Томскую духовную консисторию сообщалось, что «…новостроящийся в селе Брюхановском храм во имя Святыя Живоначальныя Троицы постройкою вчерне окончен». Этап отделочных работ был также непродолжителен и закончен к сентябрю этого же года. В долгожданный день 18 февраля 1910 г. по благословению Томского епископа Макария благочинный протоиерей Леонтий Попов в сослужении клириков Томской консистории и других благочинии совершил торжественное освящение Свято-Троицкой церкви.
В 1930-е гг., по воспоминаниям местных жителей, он был расстрелян как враг народа. Со здания снимаются главки, колокольня, завершения храмового объема, и многие годы оно использовалось под склад Заготзерна, мастерские МТС, под районный Дом культуры с библиотекой. С 1970-х годов заброшенное здание разрушалось. В 1980 г. здание предполагалось приспособить под Дворец бракосочетания. Первые службы начались в деревянном молитвенном доме с 1990 г.
После восстановления самостоятельного прихода в 1992 г. настоятель о.Владимир Рассказов начал реставрацию здания по проекту архитекторов В.Н. Усольцева и П. Г. Тиманова.
До сих пор в селе помнят, как вокруг храма лежали доски, кирпич и другие стройматериалы, но никому и в голову не приходило что-то утащить: дело-то Божье! Все ждали восстановления церкви.
В 1995 г. каменный храм был освящен Владыкой Софронием. Вокруг отреставрированного храма сделали каменно-металлическое ограждение. На благоустроенной территории высадили липы. Продолжались работы по изготовлению и росписи иконостаса московскими и новокузнецкими иконописцами.
8 июня 1998 г. Архиепископ Софроний освятил отреставрированный храм.
