Указом от 13 июня 1839 года было получено разрешение на строительство кладбищенской церкви во имя Св. Апостолов Петра и Павла. Сумской купец Федор Сапожков изначально пожертвовал на строительство храма 500 тысяч рублей. Затем в мае 1843 года был определен состав попечителей строящегося Петропавловского храма – купцы Федор Сапожков, Иван Курносов, Андрей Копылов и Федор Стожков. Строительство велось под председательством протоиерея Петра Марецкого. Храм был освящен в октябре 1851 года Преосвященным Филаретом (Гумилевским), архиепископом Харьковским и Ахтырским. При храме была домовая церковь во имя Св. Иоанна Предтечи, устроенная в здании местной богадельни, построенной И. Г. Харитоненко.

В непосредственной близости к храму находятся могилы членов семьи Харитоненко. Великолепные мраморные скульптуры выполнены французским скульптором Аристидом Круази. Работы этого скульптора украшают Парижскую мэрию, сады Пале-Рояля и Лувра в Париже. Они были привезены П. И. Харитоненко в 1900 году из Парижа, со Всемирной промышленной выставки. Одна из них установлена на могиле дочери Павла Ивановича – Зинаиды, умершей в малолетнем возрасте. Вторая – на могиле его отца, Ивана Герасимовича. Здесь же похоронен и сам Павел Иванович Харитоненко.

Со стороны алтарной части храма находится могила другого известного благотворителя нашего города – купца Дмитрия Ивановича Суханова, попечителя и многолетнего старосты Спасо-Преображенского собора, много сделавшего для его благоустройства. Есть мнение, что автором памятника на его могиле является известный скульптор П. Антокольский. Там же рядом находятся могилы первых правящих архиереев Сумской епархии, созданной в 1945 году – Илариона Прохоровна и Евстратия Подольского.