У повоєнний період у низовині під поселенням Карасівка (нинішня Новосьоловка) релігійній громаді віддали одноповерховий житловий будинок далеко від історичного центра Маріуполя. У 1946 році будинок переобладнали під невелику церкву.
Названий храм був на честь Святого Миколая, який є не тільки чудотворцем, але й покровителем моряків та рибалок. Малий храм діяв без збільшення до кінця 1980-х рр.
У 1989році церкву почали перебудовувати, а в 1991 році оновлений храм освятили.
Храм будували на кошти вірян. Замову на проект собору отримали архітектори Клюєв А. Д. та Еренбург Н.Ю. Храм вибудовано у вигляді латинського хреста або у вигляді спрощеної базиліки. Прагнення дотриматись усіх православних канонів привело до неузгодженого розташування малих куполів на даху поряд із завеликим, непропорційним центральним.
Храмова споруда не стала творчим досягненням архітекторів і не стала вартісною архітектурною окрасою міста.
Дзвіниця вбудована у храм над західним фасадом. Собор вибудовано з цегли, як і приміщення причта та малою церквою при ньому. Разом із собором споруди утворили храмове подвір’я, обнесене парканом із декоративними ґратами.
Дотримання православних канонів найбільше відбилося на стінописах. В них були абсолютно відкинуті напрацювання релігійного живопису доби російського бароко, класицизму чи академізму, тобто відкинутий досвід трьох століть попереднього розвитку і стилістичного дотримання. З декоруванням вибудованого собору упорались до зими 1993 року.
Художникам надали програму створення храмових стінописів у стилістиці 17 століття, тобто пізнього середньовіччя із зворотньою (візантійського типу) перспективою. Над створенням стінописів працювала бригада місцевих художників, серед котрих були — Бараннік С. О., Бондаренко А. Г., Ільчинський С. В., Яценяк Л. Л., Лопато В. В., Фасулакі А. Е., Ведькал А. Н.
Декоративні ґратки паркана створені під керівництвом майстра Овчаренка Е.Б.
Серед святинь собору значаться Маріупольський образ Божої Матері, частини мощів Миколая Чудотворця, Оптинських старців та святителя Митрополита Ігнатія, який перевів греків із Криму до Приазов’я.
