Деревянная Никольская церковь была возведена в Якутске в 1718 году, одной из первых в городе, за Ратушной площадью около острога. В середине XVIII века в Якутские упоминается церковь «Николая Чудотворца с богадельнями».
Со временем деревянное здание храма, вероятно, пришло в ветхость или сгорело. Тогда по сложившейся традиции горожане в 1791 году стали возводить новое каменное здание храма, которое, по-видимому, за скудостью средств строилось более тридцати лет. Строительство велось на месте где впоследствии расположился Институт геологии Якутского научного центра Сибирского отделения Российской академии наук. К осени 1821 года завершилось строительство верхнего этажа и произошло освящение трёх верхних престолов. Огромная церковь претендовала на главенствующую роль в композиции города. Но из-за непрочности фундамента она начала разрушаться после землетрясения, в её стенах и каменных сводах появились трещины. Комиссия, обследовав здание, пришла к выводу, что «строитель оного не обратил должного внимания на основание или фундамент как наиважнейшую часть в каждом строении.» Якутское областное правление, получив соответствующее указание из Иркутска, в 1834 году вынуждено было дать распоряжение о разборке стен здания церкви. Об архитектуре недостроенной церкви известно, что нижний этаж имел 18 окон, верхний этаж — 20 окон; высокий четверик имел два этажа с шестью престолами; сверху был устроен восьмерик. В храме имелось 9 колоколов, в том числе «большой колокол, на коем весу неизвестно, и полиелейный колокол весом 66 пудов 18 фунтов».
Вскоре предложение о сооружении нового Никольского кладбищенского храма, предназначенного для совершения погребальных обрядов, было поднято одним из богатых людей города купцом 2-й гильдии Иваном Яковлевичем Шиловым, что было поддержано горожанами, собравшими необходимую сумму путём пожертвований. Летом 1843 года Якутск с ревизией дел духовенства посетил архиепископ Иркутский Нил Исакович, поддержавший начинание. В городе развернулось производство кирпича, началась выемка бутового камня в Табагинском мысе, стали создаваться артели рабочих-каменщиков. 9 мая 1847 года духовенство города освятило фундамент здания, а в 1851 году возведение церкви в основном было завершено. Купец Шилов сам выбирал место для стройки, приобретал материалы, контролировал ход работ. В 1852 году в Якутск прибыл архиепископ Камчатский святитель Иннокентий Вениаминов, который 9 мая того года освятил главный престол, а 11 и 21 мая по его распоряжению благочинным священником Димитрием Хитровым и соборным священником М. Ощепковым освящены были другие два престола. Во вновь построенную церковь были перенесены из старой колокола, облачение, многие иконы. Все три иконостаса были сооружены вновь по чертежам областного архитектора Диаконова. В ограде Никольской церкви хоронили покойников из всех сословий, составлявших население города. Из преданий известно, что ктитор храма, купец Иван Яковлевич Шилов-младший, за немеркнущие благодеяния в пользу церкви был похоронен «у входа в храм по правую руку».
В 1920-е годы Никольская церковь получила печальную известность в связи с расстрелами красными в ее ограде наиболее известных представителей интеллигенции, купечества и духовенства. В те же годы церковь передали «коллективу верующих» обновленцев. С колокольни церкви в 1930-е годы были сброшены колокола. К концу того десятилетия стройки города вплотную подошли к ограде кладбища. Для расширения зоны застройки постепенно стали сносить кладбище; ещё раньше злоумышленниками были украдены памятники, установленные над могилами некоторых местных общественных деятелей. К 1939 году Никольский храм остался последним действующим в Якутске, но так-как верующие были лишены возможности полноценно ремонтировать его, кладбищенский храм закрыли под предлогом «аварийного состояния».
Когда храм был закрыт, частично перестроен изнутри и капитально отремонтирован. После этого в нём размещался партийный архив, канцелярия городской архитектуры и библиотечный коллектор, что способствовало сохранению здания. Когда в 1945-1946 годах верующие стали подавать заявления о возвращении церкви, взамен храма им был выделен молитвенный дом в частном доме И. Топоркова. В 1950-е годы последние остатки кладбища сравняли с землей. По рассказам старожилов, надгробные памятники были использованы в качестве бутового камня на стройках города, в частности под основание Якутской городской электростанции. По предложению и настоянию краеведа И. Д. Архипова, здание церкви в 1976 году было включено в список памятников архитектуры республики. В 1982 году по настоянию краеведов И. Архипова и А. Копырина ведомство, занимавшее здание, провело косметический ремонт постройки. К концу советского периода из всех ранее существовавших в Якутске православных храмов только эта церковь сохранила свой первоначальный вид и объёмы; уцелели деревянные конструкции перекрытий, железная кровля и даже кованые решётки на окнах.
Церковь была возвращена верующим в начале 1990-х годов. Патриарх Московский и Всея Руси Алексий II в 1993 году посетил храм и выразил надежду на скорое его восстановление. Правительство и президент Якутии приняли решение о выделении средств на восстановление этой церкви. Храм был вновь освящён 8 октября 1995 года и стал кафедральным собором Якутской епархии. Сохранял этот статус до 2005 года, после чего был возвращён в разряд приходских храмов, но с присвоением названия «Градоякутский». В 2010-х годах под руководством Д. А. Трофимова было обновлено внутреннее убранство храма.
