Ground breaking ceremony was held on the Feast of the Protection of the Theotokos on October 1/13, 1899. A wooden church in Central Square of New City (Noviy Gorod) section of Harbin, was completed in 1900. On December 18, 1900, the church was consecrated in the name of St Nicholas of Myra. St Nicholas Church was elevated to the status of a cathedral by decree of the Holy Synod of February 29, 1908.
St Nicholas was declared the Cathedral within the new Diocese of Harbin that was established in 1922 by ROCOR. The new diocese was administratively independent from both the Diocese of Vladivostok and the Russian Spiritual Mission in Beijing.
Also built next to the Cathedral in 1933 was the Holy Iveron Icon of the Theotokos Chapel, being a replica of the revered Moscow Chapel of the same namesake that was destroyed by the Bolsheviks in 1928.
On June 8, 1941, the monument to the fighters with the Comintern ( "Monument to the heroes who fell in the struggle against the Communist International") had its grand opening on the Cathedral Square in Harbin, opposite the hotel "New Harbin". (Rubezh, June 21, 1941. pp 13-15)
On August 23, 1966, during the Cultural Revolution, the Cathedral was destroyed by the Red Guards. Present day Square was where the original Cathedral use to stand.
According to Harbin municipal religious archive, Fr Valentin Baryshnikov served as the sixth rector, while the seventh and last rector of the Cathedral Fr Anikita Wang was martyred in 1967.
In 2007, St Nicholas Art Museum has been built at a different location as a full scale replica of the original St Nicholas Cathedral.