Одной из самых красивых на всей Транссибирской железнодорожной магистрали стала возведенная в 1898 году церковь во имя святого преподобномученика Андрея Критского на станции Тайга. Закладка первого камня в основание храма состоялась 1 июля 1897 года в присутствии Его Преосвященства епископа Томского и Барнаульского Макария и начальника работ по строительству Средне-Сибирской железной дороги действительного статского советника Николая Павловича Меженинова. Автором проекта стал известный томский архитектор Константин Константинович Лыгин, который оставил неизгладимый след в истории градостроительства не только Сибири, но и России. Большой вклад в строительство церкви (около 30 тыс. золотых рублей) внес челябинский купец Андрей Михайлович Новиков. Указом священного Синода храм на станции Тайга был открыт 18 июня 1898 года. До этой даты, по строящейся железнодорожной магистрали, курсировал специальный вагон, стилизованный под церковь. В связи с тем, что тайгинский храм стоял на так называемых землях Кабинета Его Императорского Величества, то император Николай II лично начертал одобрительный отзыв на проектный чертеж. Первым священником стал 35-летний воспитанник Томской духовной семинарии Сергей Семенович Соколов. Его перевели в Тайгу из Каинска (ныне город Куйбышев Новосибирской области).

Печальна судьба храма стала в связи с установлением советской власти. Разграблены иконы, потерялись золотые и серебряные оклады. Поруганный храм превратили в железнодорожный склад. Одно время его хотели взорвать, но качество кладки позволило выдержать варварское отношение господствующих безбожников к одной из лучших церквей на всей магистрали от Челябинска до Владивостока.

В 1991 году было принято решение о восстановлении церкви и передаче ее в собственность Кемеровской и Новокузнецкой епархии. Настоятелем церкви стал человек, внесший огромный вклад в ее восстановление – протоиерей Игорь Лаврык.

Церковь Андрея Критского наряду с вокзалом станции Тайга, локомотивным депо, и лавкой купца Магазова входит в туристский маршрут по историческому центру города Тайга.