В 1799 году была заложена, а в 1800 году была построена однопрестольная каменная церковь во имя Рождества Богородицы за счет пожертвований российских купцов, поэтому ее еще называли «Старокупеческая». Строителем церкви был протоиерей Карп Павловский. Общая высота храма 38 метров. Храм имеет мощные стены из тесаного камня-ракушняка. Колонны изначально были позолочены. В 1828 году к главному в честь Рождества Пресвятой Богородицы приделу были достроены еще два придела. Левый был освящен в честь святых царей Константина и Елены, а правый — в честь святителя Митрофана епископа Воронежского. В этом же году церковь получила статус Собора. В 1835 году, когда возник вопрос о названии улицы, на которой находится Собор, Г.Г. Автономов предоставил на утверждение адмиралу М.П. Лазареву проект, в котором эта улица получила название Рождественской в честь Собора Рождественско-Богородичного.
При соборе было учреждено в 1874году церковно-приходское попечительство, почетным членом которого в начале 20века состоял настоятель Кронштадтского собора протоиерей Иоанн Сергиев, ныне – прославленный святой праведный Иоанн Кронштадтский.
Расположен храм в исторической части Николаева, т.н. «Городовой», на перекрестке ул. Рождественской Лягина и Купеческой Потемкинской. Когда в 1922 году происходило изъятие церковных ценностей в фонд помощи голодающим община собора сдала 172 кг. серебра. 31 января 1930 года власти сняли колокола весом 10,2 тонн цветного металла, а 8 ноября 1936 года собор был закрыт. В довоенное время здание собора использовали как гарнизонный Дом Красной Армии и Флота, после войны оно получило название «Дом офицеров».
В начале 90-х годов собор передан Украинской Православной Церкви МП и с тех пор полюбился многим горожанам. В нем находятся мощи священномученика Сергия пострадавшего за веру, а также частица мощей св. прав. Феодора Ушакова.
