Ще 1887 року на кладовищі було збудовано невеличку капличку, яка, втім, була замалою і не могла задовольнити існуючі потреби. Тому 1910 року полковник Іван Мирович запропонував власним коштом (він виділив 750 рублів) переобладнати капличку на церкву за умови, що храм буде освячено в пам'ять Святої Катерини, на честь якої було названо його покійну дружину. У грудні 1910 року рішення про це було прийняте, а вже 18 квітня1911 року церкву було освячено. Це була одновівтарна церква з дерев'яною триярусною дзвіницею. 1913 року у храмі сталася пожежа. На час відновлювальних робіт богослужіння проводилося у склепі-каплиці родини Сольських, яка пізніше стала діючим храмом кладовища.
1974 року (за іншими даними — 1972 року) церкву було знищено, а на цьому місці влаштовано символічний воїнський меморіал.
Нині побудована нова церква, ведуться роботи по її облаштуванню.