Одигитриевская церковь, заложенная в 1775 году, стала первым каменным строением Кузнецка. Большую часть средств на ее постройку (400 рублей) дал разбогатевший крестьянский сын, купец и «доброхотодатель» Иван Муратов. Для возведения храма была приглашена одна из лучших артелей каменщиков во главе с мастером Почекуниным.
Архитектура каменной Одигитриевской церкви представляла собой классический пример сибирского барокко периода расцвета; была построена из фигурного кирпича; состояла из двух престолов: верхний престол — в честь иконы Одигитрии, нижний – в честь Георгия Победоносца. Строительство продолжалось на протяжении пяти лет и было завершено в 1780 г. Новый храм был торжественно освящен Кузнецким заказчиком священником Ефимием Викуловским. Одигитриевская церковь исполняла роль главного храма г. Кузнецка до 1835 г., когда освятили каменный Преображенский собор.