Храм этот был вторым из построенных в Белом городе приходских храмов. Само название его говорит о тесной связи храма с астраханским купечеством и находившимся в Астрахани торговым гостиным двором. Несомненное почитание торговым людом святителя Николая Чудотворца, как покровителя торговли и мореплавания, способствовало появлению храма в честь этого святого рядом с Русским гостиным двором и речными пристанями, где шла постоянная разгрузка и отгрузка товаров. Точное время построения первоначального храма неизвестно. Можно только с уверенностью утверждать, что построен он был вскоре после появления самого гостиного двора в Астрахани. По свидетельству летописца, в 1599 году во время опустошительного пожара в остроге сгорели гостиные дворы, русский, бухарский, гилянский. Так что в конце XVI века гостиный двор уже существовал в городе. Более вероятно, что первый, ещё деревянный, Николаевский храм был построен в начале XVII века и 1628 годом датируется первое упоминание о нём.
В начале XVIII века началось строительство новой каменной церкви. Инициатором постройки храма выступил митрополит Сампсон, сумевший уговорить высших представителей астраханского купечества того времени профинансировать это богоугодное дело. Самому митрополиту не удалось увидеть завершение начатого им строительства, хотя основные работы ко времени его кончины в 1714 году были уже завершены. Уже при его преемнике епископе Иоакиме 5 ноября 1714 года был освящён левый придел во имя Великомученика Георгия. Дальнейшие работы затянулись надолго, и только 23 июня 1721 года был освящён главный храмовый престол во имя Святителя Николая. Возможно, этому поспособствовал намечавшийся в 1722 году приезд в Астрахань императора Петра I. К его приезду астраханский губернатор Артемий Волынский старался привести город в более благоустроенный вид. В июне 1755 года в трапезе храма с правой стороны был устроен придел в честь иконы Божией Матери «Всех Скорбящих Радосте». Устроен он был по обету, данному коллежским советником и товарищем астраханского губернатора Михаилом Фёдоровичем Гневашевым. В том же году 12 ноября придел был освящён архимандритом Иоанно-Предтеченского монастыря Аароном. Со временем храм несколько раз перестраивался и подновлялся.
В 1971 году исполком Астраханского горсовета, «руководствуясь заключением о техническом состоянии бывшего здания церкви Никольской, проведённым инженером-экспертом облотдела по делам строительства и архитектуры тов. Бор-Раменским 8 июня 1970 года, учитывая ветхое, аварийное состояние всех основных несущих конструкций здания церкви и невозможности её дальнейшей эксплуатации, а также начало строительства ресторана на 450 мест решает, разрешить областному управлению торговли переданное на баланс здание бывшей церкви Никольской по ул. Халтурина, дом 2/3 разобрать». В этом заключении горсовета было очень много неправды, так как эксперт инженер О.К. Бар-Раменский наоборот настаивал на сохранении общего объёма храма при капитальном его ремонте. Действительно, храм мог простоять ещё очень долго, если бы управление торговли не наметило построить на его месте торговый центр с рестораном. Ломали храм долго, массивные стены с трудом поддавались разрушительному натиску. Верующие астраханцы приходили на место трагедии и подбирали кусочки штукатурки с сохранившейся на ней росписью, которые с благоговением уносили к себе домой как святыню. В 1974 году от церкви не осталось и следа.
Гостино-Николаевский храм оказался последним по времени из других православных храмов, уничтоженных за время коммунистического правления. Сейчас на месте храма стоит современное, из стекла и бетона, здание центрального универсама.
