Деревянная церковь Одигитриевской иконы Божьей Матери была построена в г. Кузнецке в 1676 г. в честь избавления от «морового поветрия» (эпидемия чумы) и к середине XVIII в. изветшала «…до такой степени…, что зимой на образах иней, а свечи задувает ветром».
10 января 1773 года прихожане подали прошение о строительстве нового каменного храма. Под прошением подписались церковный староста Иван Муратов, бургомистр Яков Сорокин, ратман Михаил Ананьин, сын боярский Дмитрий Конюхов и другие «…лучшие люди из купцов, разночинцев и крестьян».
Средства для постройки храма должны были собрать как сами прихожане, так и специальные сборщики, отправившиеся в разные уголки Тобольской епархии с разрешения епископа Тобольского и Сибирского Варлаама.