История храма охватывает более века и включает периоды строительства, закрытия, разрушения и последующей реставрации.
Строительство храма было инициировано вдовой каинского купца I гильдии Ивана Васильевича Шкроева — Александрой Ивановной Шкроевой. В соответствии с завещанием её супруга, на строительство церкви было выделено 60 000 рублей, а дополнительно 29 000 рублей предназначались для содержания причта. Строительные работы завершились в 1904 году. 18 ноября того же года архиепископ Томский и Барнаульский Макарий (Невский) освятил новосооружённый храм во имя святого Пророка и Предтечи Господня Иоанна.
После завершения строительства храм был осмотрен исполняющим должность архитектора губернии Кондаковым и младшим инженером строительного отделения Томского губернского управления Андреем Дмитриевичем Крячковым, впоследствии ставшим известным архитектором. На осмотре также присутствовал настоятель Спасского собора протоиерей Николай Вавилов.
Приход церкви охватывал территорию города Каинска (ныне Куйбышев) и к 1911 году насчитывал 551 прихожанина. Церковную службу осуществляли один священник и один псаломщик. На колокольне храма размещалось шесть колоколов, самый большой из которых весил 1697 кг.
В 1938 году храм был закрыт. В период советской власти здание церкви использовалось под зерносклад, кинотеатр и краеведческий музей. В этот период были разрушены колокольня, пятиглавие храма и главка над алтарной частью. Южный фасад позднее был закрыт кирпичной пристройкой, часть окон заложена кирпичом.
В 1990 году храм был возвращён верующим. С 1995 по 2010 год в разное время в церкви проводились восстановительные работы. В 1995—1998 годах при реконструкции колокольни были допущены отступления от первоначального проекта. В 1999 году Научно-производственный центр по сохранению историко-культурного наследия под руководством С. Н. Богомазова выполнил проект по реставрации здания. Автором проекта был инженер А. Б. Демьяненко, который предусматривал восстановление первоначального облика храма с рекомендациями по отделке интерьера. С 2003 по 2005 год проводилась реконструкция глав. В 2008 году была демонтирована поздняя пристройка с южной стороны, а в 2010 году выполнена реставрация фасадов.
Архитектурно храм представляет собой бесстолпное здание с трёхчастной продольно-осевой композицией, включающей четверик с семигранной апсидой, трапезную и ярусную колокольню, размещённую поверх притвора с двумя приделами. Из семи луковичных глав церкви пять возвышаются над главным храмом, по одной — над колокольней и алтарём. Стены храма выполнены из кирпича «под расшивку». Перекрытия основных помещений представлены сводами: восьмилотковым с распалубками для кафоликона, цилиндрическим с надоконными распалубками для трапезной и сомкнутым для колокольни. Стены завершаются ступенчатым профилированным карнизом с сухариками. Крыша церкви имеет сложное очертание, по её металлической кровле проходит диагональный рисунок. Водосток организован снаружи.
Элементы фасадов выполнены из лекального кирпича с различными обломами. Полуциркульный портал входа и приделы с южной и северной сторон храма фланкированы пилястрами, которые служат опорой для килевидных профилированных закомар. Опирающийся на пилястры многопрофильный архивольт килевидного завершения объединяет трёхчастные окна со стороны южного и северного фасадов. В тимпан западного фасада помещён квадрифолий. Декор западного, северного и южного фасада кафоликона включает крестообразные филёнки. По восточным граням апсиды расположены ниши-киоты, которыми украшены также и килевидные кокошники, выступающие поверх карниза главного объёма со стороны южного и северного фасадов.
