The cathedral was built in honour of the Emperor Alexander II of Russia, who was assassinated by the political revolutionaries group Narodnaya Volya.

The construction committee, established 1 March 1890, was headed by the renowned Yalta engineer and historian Alexandre Berthier-Delagarde.

Large sums were donated by notable citizens B. V. Khvoschinsky and I. F. Tokmakov, and the land plot was gifted by Baron A. L. Wrangel.

Adjacent to the cathedral, in the style of the Russian terem, was a three-story building completed in 1908, which housed the church school in honour of Tsarevich Alexei, a shelter for tuberculosis patients, a hall for the meetings of the Alexander Nevsky Brotherhood.

The Brotherhood engaged in charitable activities, the organization of parish schools, and missionary work, and during World War I, also assisted the wounded and arranged hospitals and sanatoriums.