Первоначально Свято-Николаевская церковь была устроена в циновочном бараке на месте поселения первых русских строителей КВЖД в 1898, этот район позже получил название Старый Харбин. Затем она была перенесена в железнодорожный барак. Ее первым настоятелем был священник военного отряда о. А. П. Журавский. Новое здание церкви возвели за три месяца в 1926 благодаря усилиям прихожан и настоятеля церкви протоиерея о. В. Синайского.

Свято-Николаевская церковь была размещена на просторной площади, но не в центре, а на ее периферии и обращенная к ней своим северным фасадом. Остальные же фасады выходили на углы перекрестков улиц, перспективы которых церковь замыкала. Этот прием отражает укоренившийся в XIX в. принцип соединения двух градостроительных традиций: регулярной европейской Нового времени и ориентированной на древнерусский прием художественного освоения горнего пространства.

Архивные фотографии утраченной Свято-Николаевской церкви позволяют с определенной степенью достоверности судить о ее композиции и стилистике. По воспоминаниям одного русского харбинца, «церковь, как снаружи, так и внутри, была оформлена скромно и походила на сельскую, каких много в России». Тип храма – приходской. Первообразом, от которого оттолкнулся архитектор, послужила новгородско-псковская архитектура. Над западным притвором высится звонница, столь характерная по форме для этой архитектурной школы. Сооружение выразительно по силуэту, фасады украшают многообразные по форме и прихотливо размещенные оконные и дверные проемы. В тимпане двускатной островерхой кровли звонницы – роспись. Не смотря на симметричность сооружения, все вместе создает узнаваемый образ рукотворной живой «неправильной» северо-русской церкви.

В 1927 Епархиальное собрание обратилось к митрополиту Харбинскому и Маньчжурскому Мефодию с просьбой ходатайствовать перед китайской администрацией города отказаться от намерения размещения в помещении церкви китайской школы в целях сохранения Старо-Харбинской церкви в неприкосновенности как исторического памятника, ибо она являлась первым храмом, сооруженным в Харбине и полосе отчуждения КВЖД.

Известно, что еще в 1945 в церкви продолжались службы, последним ее священнослужителем был диакон В. М. Кармилов. Церковь разрушена.