Каменная трёхпрестольная церковь с колокольней была построена в 1838 году на холерном кладбище стараниями настоятельницы Крестовоздвиженского женского монастыря игумении Еванфии на средства монахини Сусанны (в миру Анны Александровны Рылеевой). Главный престол был освящён в честь Усекновения главы святого Пророка, Предтечи и Крестителя Господня Иоанна. Приделы были во имя святителя Николая Чудотворца, архиепископа Мир Ликийских, и святого блаженного Николая, Христа ради юродивого. Обиходное название храма не связано с медициной, как можно было бы предположить. Дано оно было по большому кресту, установленному у храма и выкрашенному в красный цвет. Кладбищенский храм Крестовоздвиженского монастыря являлся местом отпевания умерших, ведущая к нему улица, по которой шли похоронные процессии, называлась Печальной (современная Серова). 22 апреля 1855 года церковь стала приходской. В 1884 году здание было перестроено по проекту губернского архитектора С.Ф. Езеровского.
В 1912 году к храму были приписаны три школы, в штате причта состояли три священника, диакон и три псаломщика, дома для которых были церковные. В советские годы старое кладбище было застроено. Закрытый храм, мешавший строительству, был разрушен.
Сегодня от церкви не осталось никаких следов, сохранились лишь дореволюционные фотографии. Неизвестным остаётся и точное место, на котором храм находился. Располагался храм на улице Чернышевского (в прошлом Большая Сергиевская), примерно в районе Городского парка
И. Козловский, 2011 г., Большая Саратовская Энциклопедия, Справочная книга Саратовской епархии. 1912 г.