В городе Якутске Никольская церковь существовала с 1718 года и считалась одной из старейших. Находилась она в центре города и была изначально деревянная, затем была возведена двухэтажное каменное здание, которое, однако, быстро разрушилось.

В 1847 году, на средства купца И.Я.Шилова, за городом на берегу протоки, началось строительство новой Никольской церкви. 9 мая 1852 года архиепископ Камчатский Иннокентий (Вениаминов) освятил главный престол Никольской кладбищенской церкви. В ограде Никольской церкви хоронили представителей всех сословий, составлявших население города. Со временем надгробные памятники ветшали, а в советское время большая часть кладбища была снесена.

Однако все объемы храма и его первоначальный вид сохранились почти без изменений.

В 1921 году церковь передали «коллективу верующих» обновленцев. А в 1939-м закрыли совсем. С неё сняли кресты и разорили внутреннее убранство. Здание было перестроено изнутри. В нём размещался партийный архив, канцелярия городской архитектуры и библиотечный коллектор.

В начале 90-х годов ХХ века храм одним из первых возвратили возрождённой Якутской епархии.