Современный район Кировограда, который мы знаем под названием Балка, когда-то назывался Млынки, а еще раньше - Крыничатые хутора. Район этот знали в свое время как кладбищенский. Здесь были кладбища: иудейское, католическое, лютеранское, магометанское, караимское (все они находились за железной дорогой, район складов). Отдельно от них, в районе современной улицы Полтавской, был выделен участок земли для кладбища православного со своим деревянным храмом во имя святых первоверховных апостолов Петра и Павла. Построен не позднее 1773 года (именно в этом году мы встречаем первые из сохранившихся упоминаний о храме). В 1805 году на месте первого, к тому времени уже непригодного для богослужений храма по инициативе соборного причта и купца Никиты Пронина был построен новый Петропавловский храм, первым настоятелем которого стал священник Анатолий Заплатин.
До 1850 года Петропавловский храм был ''приписан" к Собору, с этого же года отделен и получил самостоятельность. А еще через 12 лет старанием купца 3-й гильдии Герасима Романченко недалеко от старого деревянного храма, небезопасного для совершения служб, был заложен новый каменный трехпрестольный храм. Строительство его завершилось в 1870 году, уже после смерти Романченко. Освящен храм во имя апостолов Петра и Павла. Согласно документам, находился храм при въезде в город но Александрийскому тракту из Киевской и Полтавской губернии.