Первое упоминание о церкви на данном месте содержится в писцовых книгах 1628 года. До этого времени на участке существовали два храма: один в честь святых Афанасия и Кирилла Александрийских, другой — святого мученика Мины. К 1794 году в указе консистории упоминается только церковь святого Мины. В этом же году было предписано разобрать ветхую деревянную церковь для обжига кирпича, предназначенного для строительства новой каменной церкви с приделом в честь святой великомученицы Варвары.
Строительство каменного храма было завершено в 1805 году. Первоначально здание имело тёсовую крышу и деревянную колокольню на каменных столбах. В 1819 году была возведена каменная колокольня, а в 1823 году тёсовая кровля была заменена на железную. В 1828 году храм был расписан. В 1858 году по желанию прихожан с северной стороны был пристроен придел в честь Введения во храм Пресвятой Богородицы.
Архитектурно храм представляет собой кирпичное оштукатуренное здание на белокаменном цоколе с белокаменными деталями. Основной объём выполнен по типу «восьмерик на четверике», при этом восьмерик в полтора раза выше несущего объёма. Симметричные фасады четверика разделены лопатками, угловые лопатки покрыты ленточным рустом и заглублены от фасадной плоскости. На каждой грани восьмерика расположены крупные арочные окна, фланкированные сдвоенными пилястрами. Грани завершены антаблементом с плоским фризом под высоким карнизом.
В советский период храм был закрыт. В 1940–1960-х годах были уничтожены трапезная, приделы и колокольня. Оставшаяся часть здания использовалась под различные нужды: в 1950-х годах — архив ЗАГС, в 1970-х — склад отдела рабочего снабжения речного порта, позднее — мастерские. В 1976–1977 годах была проведена частичная реставрация храма.
