Духовне Правління Старокодацького Хрестового намісництва 21 травня 1774 року (за старим стилем) просило дозволу у Київського митрополита на будівництво церкви з середнім престолом в ім’я Пресвятої Трійці, лівим — в ім’я Трьох святителів і правим — в ім’я апостолів Петра і Павла. Благословенну грамоту від митрополита Гавриїла привіз до Самарчука ієромонах Давид. Кошовий Петро Калнишевський у листі до київського генерал-губернатора просив дозволу посланцям від Січі на купівлю дерева для будівництва. Дерево сплавили Дніпром до гирла Самари і привезли до містечка взимку 1773–1774 р. Місце для храму вибрали на високому місці, недалеко від берега річки, в центрі містечка, щоб споруду було добре видно з усіх боків.
Для будівництва храму запросили талановитого зодчого з містечка Нові Водолаги (колишня Харківська губернія) — козака Якима (Іоакима) Погребняка. Після освячення і закладки почалося будівництво церкви. Її будували поволі. Г. Надхін вказує, що у 1775 році її вивели «по вікна». Місцеві мешканці продовжували відвідувати стару церкву, яка стояла з 1734 року. Церква-попередниця була маленька, теж дерев’яна й крита очеретом.
Будівництво нової соборної церкви через багато обставин було завершено вже після скасування Запорозької Січі 1778 року. Нова споруда складалася з дев’яти високих башт, кожна з яких мала чотири яруси. Середні башти вищі, ніж бічні, а центральна найвища. Дерев’яні соснові зруби збудували на дубових підставах (стовпах), «…щоб вітер вільно гуляв під долівкою, або помостом, і просушував вогкість і вологу під спорудою». В основі стовпів було встановлено кругле каміння (пізніше, під час реконструкції у 1830-му році під дубові підвалини було заведено цегляний фундамент).
Спочатку дахи собору були криті дубовим гонтом (дерев’яні дощечки, в даному випадку прямокутної форми). Цей дах простояв понад 50 років, а у 1830-му році дахи вкрили залізом і пофарбували зеленою фарбою. Кожна з дев’яти башт мала купол завершений глухим ліхтарем. Усі дев’ять завершень-верхів було позолочено в 1830-му році (до цього часу металеві завершення були пофарбовані у зелене), пізніше у 1850-му році позолоту поновили. Позолоченими були металеві хрести на верхах, усі чотирьохкінцеві з випуклими дуговими раменами, із зорями на кінцях рамен та промінцями в прямих кутках.
У 1778 році встановлено й освячено в головному престолі іконостас, перенесений зі старої Троїцької церкви. У 1780 році виготовлені й освячені нові іконостаси в бічних притворах, а також розпочато монтаж нового головного іконостасу середнього притвору. Вівтар займав майже третину загального простору храму, його було розділено двома поперечними стінами (кожна з двома прогонами). Триярусний іконостас із золоченими пілястрами, карнизами і різьбленою каймою був справжнім витвором мистецтва. Завдяки фотографіям дослідника церковної старовини В. Машукова сьогодні маємо уявлення про зовнішній вигляд цієї пам’ятки декоративного мистецтва. З освяченням нового іконостасу головного притвору 18 квітня 1781 року (за старим стилем) будівництво храму було завершено.
Стіни Троїцького собору прикрашала велика кількість старовинних ікон. Дослідники виділяли три найбільш цікавих і старих — запорозьких часів — Спасителя, Божої Матері та Святого Миколая. На останню чверть ХІХ ст. найбільше шанувалися дві ікони: Іверської Пресвятої Богородиці та Святого Миколая, що молиться. Обидві ікони постійно використовували при хресних ходах і брали до хат для освячення помешкань.
Велика кількість вікон на фасаді сприяла зоровому підвищенню об’єкта, малі вікна створювали ефект масштабності споруди. Виходячи з того, що вікна виступають показником масштабності, так само як і двері, було зменшено вікна верхніх ярусів, що також створювало оптичний ефект перспективного збільшення висоти. До собору вело троє вхідних дверей з дубового дерева, які прикрашалися кольоровими розписами. На різьблених одвірках виконано виноградні гілки з китицями винограду. Пізніше одвірки було замінено, а двері оббито залізом.
Д.І. Яворницький залишив стислий опис Троїцького собору: «Архітектура церкви проста: ні колон, ні прикрашень; з зовні церква була обшальована і пофарбована білою фарбою; з середини стіни і склепіння її розписано було картинами релігійного змісту. Іконостас зведено до склепінь, з різьбою і різними фестонами, завитками і іншими хитрощами столярного мистецтва. Живопис на ньому зроблений в старовинній візантійській манері. Висота церкви 31 сажень... При церкві пізніше було окремо поставлено дзвіницю з шістьма дзвонами, з яких найбільший важив 262 п. і 24 ф… два будинки, дерев’яну огорожу і за огорожею криницю з дерев’яним наметом. Дзвіниця, криниця, також як і собор, пофарбовані білою фарбою (їх добре видно на відомому малюнку Васильківського «Соборна площа у м. Новомосковську» – О.Х). Ззовні, на стіні, коло західних дверей, повішено чавунне «било» з прикрашенням зверху, у вигляді двох конячих голів». Зараз било зберігається в експозиції Дніпропетровського історичного музею ім. Д.І. Яворницького.
На початку 1880-х років виникла потреба в новому капітальному ремонті собору, було проведено торги на ремонт храму, в яких переміг Олексій Пахучий, однак, на момент початку робіт собор було повністю розібрано, а технічна документація та кресленики не було виконано. Тож наново собор відновлювали за фотографією, яку перед початком робіт у 1883–1884 роках на замовлення Одеського Археологічного Товариства зробив фотограф із Катеринослава Іванов. Восени 1888 року нову споруду собору було освячено. Його «ремонт» обійшовся у 75 000 рублів.
Храм зі складною та трагічною долею й досі вражає своїми масштабами і величчю. Історія пам’ятки віддзеркалює всю драматичну історію Запорозького краю і української народної архітектури.