Вже через три роки після заснування міста з’явилася офіційно зареєстрована католицька громада, яка вела активне релігійне, культурне, просвітницьке та суспільне життя. Вона стала однією з перших християнських парафій в Миколаєві. У 1794 р. один з державних будинків був переданий католицькій церкві, безперечно, з метою залучення в місто поселенців цього віросповідання, в основному з країн Західної Європи. Цей будинок був перебудований у перший католицький храм Святого Йосипа і освячений 20 травня 1796 року. Він знаходився на місці двору нинішнього костьолу, виходив фасадом на вулицю Молдаванську (нині – Декабристів).
Із 1874 року настоятелем, протягом багатьох років, був священик Никодим Черняхович, який вважав за необхідне будівництво нового храму. 1880 року він отримав дозвіл на початок збору грошей. Будівельні роботи почалися 1891 року. 1893 року будівля була зведена, а 1895 – остаточно завершена. Нова Миколаївська церква була урочисто освячена у вересні 1896 року.
Церква була побудована в еклектичному стилі за проектом Одеського архітектора Владислава Домбровського. У церкві був встановлений новий орган, німецького виробництва, вартістю 100 тисяч рублів.
Парафіяльна школа діяла з часу заснування церкви, тобто з кінця XVIII століття. Кількість віруючих постійно збільшувалася: 1875 року вона складала 2354 чоловіки, а на 1912 рік налічувалося вже 8000 чоловік.
Після революції почалися гоніння і репресії проти католиків, оскільки більшовики нещадно втручалися в справи церкви.
Мізерні архівні матеріали тих літ закінчуються лаконічним рішенням міськвиконкому: «Миколаївський римсько-католицький храм закрити». Рішення ухвалене в жовтні 1935 року.
Отже, в будівлі храму почалося нове, світське життя. Новий власник – міський історико-археологічний музей.
Почалася друга світова війна. Окупанти спершу відкрили храм для богослужінь, а потім закрили його і влаштували в храмі бійню.
Після війни храм знаходився у віданні міськвиконкому. Спочатку воно було передано військово-будівельній організації під клуб, потім – обласному управлінню профтехосвіти під Будинок культури. З метою розміщення чиновницького апарату, в будівлі була проведена «реконструкція». Прекрасне приміщення з унікальною акустикою було перегороджено горизонтальним перекриттям, і на другому поверсі, що утворився, був розміщений великий зал. На баштах, замість хрестів, повісили зірки, на місці вівтаря влаштували сцену. У такому вигляді будівля простояла до часів Перебудови.
У середині 80-их років католики Миколаєва звернулися до властей з проханням про офіційну реєстрацію римсько-католицької общини і повернення храму. І лише 25 листопада 1991 року облвиконком ухвалив рішення про передачу будівлі храму місцевій католицькій общині. 15 лютого 1992 року храм урочисто освятив єпископ Кам’янець-Подільський, отець Ян Ольшанський. Першочерговими задачами були ремонт храму і формування общини. За ці роки розібрали залізобетонне перекриття; були встановлені хрести на дзвіницях, замінений дах, проведено внутрішнє штукатурення, білення, побудований гараж. У місцевих художників замовлені прекрасні скульптури, відреставрували вхідні двері, було встановлено акустичне устаткування.
2005 року настоятелем храму став отець Ярослав Гижицький. Він провів підготовчу роботу для встановлення дзвонів, які були освячені 2006 року о. Юрієм Нагорним, з нагоди 110-річчя храму. Німецькі католики з міста Бохума подарували великий орган. Інструмент вироблений 1950 року фірмою Братів Штокман з м. Верль у Вестфалії. 28 березня 2009 року орган був урочисто освячений єпископом Броніславом Бернацьким.
