Лише завдяки писемним джерелам та кільком відомим на сьогодні фотографіям ми маємо змогу уявити собі зовнішній вигляд верхньодніпровських культових споруд. На жаль, виявити колишнє місце розташування у міській забудові цих споруд на сьогодні дуже важко. По-перше, відсутні картографічні матеріали, що проливають світло на старовинні містобудівні аспекти, по-друге, місто (центральна частина) зазнало значних перетворень у переплануванні. Навіть місце останньої цегляної Свято-Успенської церкви, що за багатьма даними знаходилася на ділянці сучасної 1-ї загальноосвітньої школи міста, можна уявити тільки приблизно. Про місцезнаходження перших храмів міста на сьогодні мало щось можна сказати, це стане можливим лише після опрацювання значної кількості джерел, розпорошених по архівних зібраннях Росії та України.
За матеріалами, які опрацьовано на сьогодні, можна припустити, що стара дерев’яна Свято-Успенська церква знаходилася на північ від нової, близько до перехрестя сучасних вулиць Яцковського та К. Лібкнехта.
Найзагадковішою на сьогодні є найстаріша з відомих нам церков Верхньодніпровська – церква в ім’я рівноапостольних царів Костянтина та Єлени. У якому місці її спорудили, поки що невідомо!
З праці відомого дослідника церковної історії Катеринославщини Феодосія Макаревського можна отримати деякі данні про вказану споруду.
Ще у 1792 році мешканці казенної слободи Новогригорівка під керівництвом сільського старшини сержанта Василя Яковлєва та поважних представників поселення Герасима Юдина, Гната Лелюхина, Тита Чернякова та інших, на загальне бажання, поставили питання про будівництво церкви в слободі та відкриття власної парафії, оскільки весною і восени відвідувати Свято-Миколаївську церкву поселення Пушкарівка не було можливості через повінь і розлиття річки Самоткані.
Спочатку громада придбала стару, але міцну будівлю храму зі слободи Богоявленської, що знаходилася в Олександрійському повіті у власності генерал-поручниці Репнінської. Потім для майбутнього причту, було відмежовано 120 десятин землі. У формальному донесенні від 4 серпня (ст. ст.) 1793 року, направленому на ім’я правителя Катеринославського Намісництва В.В. Коховського, громада на чолі з означеними вище особами просила його сприяти перед преосвященним Гавриїлом, дозволу і благословення на влаштування церкви в ім’я рівноапостольних Костянтина та Єлени.
Резолюцією від 31 серпня (ст. ст.) 1793 року Гавриїл благословив та дав дозвіл на влаштування дерев’яної церкви в ім’я царя Костянтина та його матері цариці Єлени. Тож 10 жовтня (ст. ст.) 1793 року на відмежованій ділянці у зручному місці відбулася закладка й освячення майбутньої споруди. Освячення проводив протоієрей Катеринославського духовного правління Іоанн Станіславський.
Трохи більше ніж за місяць зруб церкви було виведено вище вікон до заломів. З цього опису важко говорити про зовнішній вигляд церкви, невідомим залишається кількість зрубів, їхня висота та конфігурація. Якщо у майбутньому пощастить віднайти місце розташування споруди, то можливо за допомогою археологічних розкопок будуть встановлені архітектурно-планувальні особливості церкви. Зараз відомо лише про існування «заломів» у дерев’яній споруді, це конструктивна риса храмів, характерних для традиційних запорозьких та й взагалі українських церков. Перехід від зрубу стін до залому виконувався за допомогою ригелів та похилих клинів. Іноді в одному храмі використовували як похилі клини так і ригелі. Тож, якби була відома форма зрубу у плані, можна було б гіпотетично встановити конструктивні особливості споруди.
Нічого не згадується також про дзвіницю, ймовірно вона була найпростішої конструкції – на двох стовпах. Так чи інакше дзвіницю в той час влаштовували окремо від церкви. Це давня традиція, яка проіснувала на теренах Запорожжя-Катеринославщини до початку ХХ ст., хоча у більшості випадків традиційні храми замінювалися, перебудовувалися на новий єпархіальний лад, коли дзвіниця прибудовувалася з західної сторони церкви.
24 грудня (ст. ст.) 1793 року у трапезній церкві Святої Трійці Полтавського Хрестовоздвиженського монастиря, метрополіт Катеринославський преосвященний Гавриїл рукоположив Лаврентія Базарянінова у священики до церкви воїнського Новогригорівського поселення.
19 лютого (ст. ст.) 1795 року парафіяльним священиком та парафіянами направлене прохання до Катеринославського Духовного правління на дозвіл освячення повністю збудованої церковної споруди. Також вказувалося, що в церкві було потрібне церковне начиння і встановлено старий іконостас, який придбали разом зі старою Богоявленською церквою: «…іконостас старий, але ще здібний…». Того ж дня благочинним священиком Г. Щасливцевим подано рапорт на ім’я преосвященного Гавриїла з описом всіх церковних речей Новогригорівського храму.
Резолюцією від 25 лютого (ст. ст.) дозволено освятити нововлаштовану дерев’яну церкву у солдатській слободі Новогригорівці, що й було зроблено 17 березня (ст. ст.) того ж року Катеринославським протоієреєм Іоанном Станіславським соборним.