Перша дерев'яна церква (грецька) в тогочасному Миколаєві з'явилася в 1790 році на пожертви грецької громади й була освячена в ім'я Святого Миколая. Вона розташовувалась на розі нинішніх вулиць Пушкінської та Потьомкінської і діяла до середини XIX століття.
У 1808 році почалося будівництво нової кам'яної Грецької церкви, оскільки стара дерев'яна церква не відповідала потребам прихожан. Церква будувалася на пожертвування населення міста, роботи були завершені в 1817 році. Нині це — Свято-Нікольський собор.
У 1825 році на території тогочасного Миколаєва було вже шість церков. Окрім парафіяльних, будувалися домові храми при навчальних закладах і військових частинах. До Жовтневого перевороту в Миколаєві діяло 26 православних церков і 3 молитовні будинки. За часів СРСР більшість з них було або закрито, або повністю зруйновано. Руйнування тривало до середини 1980-х років.
1948 року утворилася Кіровоградсько-Миколаївська єпархія в нових адміністративно-територіальних кордонах. До її складу увійшов Миколаїв і частина нинішньої області. Правлячі архієреї мали титул «Кіровоградський і Миколаївський». Після утворення єпархії з адміністративним центром у Миколаєві в області активніше почало відроджуватися церковне життя.
Ще одна мечеть в місті була побудована на кошти Морського Міністерства Російської імперії для «суспільства військових мусульман Миколаївського морського порту». У лютому 1862 року Миколаївський морський порт передав спільноті територію напівзруйнованої колишньої жіночої лікарні під № 169 (номер ділянки, на якій знаходилась лікарня)[2][3]. У доповідній і пояснювальній записках головного архітектора міста Гольштина, спрямованих в Управління у справах архітектури при РНК УРСР в 1945 році є відомості про те, що мечеть повністю знищена, залишився тільки мінарет, «хоча в дуже занедбаному і ветхому стані», в якому знаходився тригонометричний пункт[3]. Згідно з «Актом обстеження татарської мечеті архітектором-консультантом у справах архітектури при Раді Міністрів УРСР Д. Криворучко», який було складено 17 серпня1946 року, мечеть була розібрана місцевими жителями в 1920-их роках, а мінарет, що залишився, перебував у занедбаному вигляді. Згодом вежа мінарету була визнана пам'ятником культури місцевого значення.