Постройка храма в честь Святителя Николая, ныне кафедрального собора, была начата обществом Китайской железной дороги в 1899 году весной, тотчас по получении заготовленных в Петербурге планов и чертежей.
Собор строился в так называемом древне-вологодском стиле специальными русскими артелями. Торжество освящения начала постройки собора состоялось в день праздника Покрова Пресвятой Богородицы 1-го октября 1899 года. На восточной стороне храма прибита медная доска с надписью; «Во имя Отца и Сына и Святого Духа основася сия церковь в честь и память иже во Святых Отца нашего Николая, архиепископа Мирликийского чудотворца, в шестой год царствования Благочестивейшего Самодержавнейшего Великого Государя нашего Императора Николая Александровича и в 25 год царствования Гуанг-Сюй в Китае, разрешением Протопресвитера морского и военного духовенства Александра Алексеевича Желобовского, при министре финансов Сергее Юльевиче Витте, при представителе Станиславе Ипполитовиче Кербедзе и главном инженере-строителе Александре Иосифовиче Югович в лето от сотворения мира 7407, от рождества же по плоти Бога Слова 1899 году октября 1-го дня в железнодорожном посёлке Сунгари архитектором Алексеем Клементьевичем Левтьевым, по освящении (места закладки) священниками Охранной Стражи Александром Петровичем Журавским и Стефаном Михайловичем Белинским. Временные мастерские. Сунгари».
Постройка храма окончилась в декабре 1900 года и 5 декабря церковь освящена с разрешения Протопресвитера военного и морского духовенства, по благословению Преосвященнейшего Евсевия епископа Владивостокского и Камчатского, в память Святителя Николая чудотворца Мирликийского старшим священником Александром Журавским, первым настоятелем этого православного храма в Маньчжурии. Престол в нём был сначала один, во имя Святителя Николая чудотворца Мир-Ликийского, празднуемого церковью 6-го декабря, а в 1923 году – другой престол в память иконы Божьей Матери «Нечаянной радости», празднуемой церковью 1-го мая.
В 1915 году был капитальный ремонт храма. Освящение отремонтированного храма состоялось 27-го сентября 1915 года Высокопреосвященнейшим архиепископом Евсевием.
В 1925 году произведён второй капитальный ремонт собора. Устроены хоры на западной стороне храма на 6 толстых деревянных столбах с ходом на хоры по новой лестнице, ведущей на колокольню.
Определением Святейшего правительствующего синода от 29 февраля 1908 года за №555 храм признан собором со штатом из протоиерея-настоятеля собора, второго священника, дьякона и псаломщика. Ещё в августе 1907 года Маньчжурские церкви были переданы в ведение владивостокского архиепископа Евсевия. По открытии временной Харбинской епархии Св. Николаевский собор был объявлен кафедральным собором с 2-го июня 1922 года. Настоятелем кафедрального собора утвержден митрофорный протоиерей Леонтий Пекарский. Ключарем собора состоит протоиерей Леонид Викторов, протодьяконом Н. Овчинкин, дьяконом С. Коростелёв и др.
Церковными старостами за всё время состояли: помощ. упр. КВжд, князь Ст. Ник. Хилков, ген. Д.Л. Хорват, инж. Б.В. Остроумов и в настоящее время Ник. Влад. Каньшин. Регентом соб. хора состоит Д.Я. Попов.