Храм во имя святителя Николая Чудотворца на Гостином дворе существовал, согласно писцовым книгам, уже в 1565 году. Точного времени постройки каменного храма установить не удалось, но архитектурные формы позволяют утверждать, что это было в XVI веке. В начале XVII века был построен придел в честь чудотворной Казанской иконы Божьей Матери. Николо-Гостинодворская церковь была теплой. В 1634 году рядом построили холодную Преображенскую церковь, которая была снесена в 1790 году из-за ветхости. В XVII веке Гостинодворский храм был богатым и процветающим, в основном, благодаря поддержке купцов, торгующих в Гостином дворе, но в XVIII веке пришел в упадок, особенно после пожаров 1742 и 1774 гг. В 1797 году приход был упразднен, а церковь приписана к Петропавловскому собору. Теперь богослужения в ней совершались редко, за исключением краткого периода в 1815-1820 гг., когда после пожара 1815 году здесь вели службы священники тоже пострадавшего от огня Петропавловского собора. К 1824 году храм был на грани полного разрушения, в 1825 году разобрана паперть.
Судьба Гостинодворской церкви решалась долго. Несколько раз епархия принимала решение разобрать и упразднить церковь, но всякий раз городские власти и гостинодворские купцы брались восстановить и благоустроить храм. В 1854 году даже был составлен проект, утвержденный Николаем I, но средств на строительство не было. Наконец, в 1861 году дело восстановления храма взяли на себя казанские купцы Федор Егорович Постников (1806-1881) и Евдоким Савватеевич Савватеев (ум. 1886). В 1864-1870 гг. Гостинодворская церковь была перестроена. Использовался ли проект 1854 года, неизвестно. Храм фактически был выстроен заново, но формы и декор XVI века в новом проекте были учтены. Известно, что иконостас новой церкви проектировал архитектор П.В. Тихомиров, вероятно, он же составил проект и самой церкви.
До перестройки Гостинодворская церковь представляла собой квадратное строение с высоким восьмериком и шатровым завершением. На литографии Э. Турнерелли 1839 года она запечатлена как квадратное в плане здание — массивный куб четверика с четырьмя маленькими главками по углам, на котором стоит низкий восьмерик с высоким шатром. Шатёр завершала небольшая чешуйчатая главка. Пирамиду шатра прорезали два ряда оконных проёмов. Пирамиду шатра прорезали два ряда оконных проёмов.
В результате перестроек к увеличенной трапезной присоединены боковые приделы, а ниже по рельефу к фасаду воздвигнута шатровая колокольня с октогоном яруса звона на высоком четверике. Из одноглавого храм стал пятиглавым и трёхпрестольным: главный престол — во имя святителя Николая Чудотворца, правый придел — в честь Преображения Господня, левый — в честь Казанской иконы Божьей Матери. Под церковью были устроены лавки и кладовые, сдаваемые в наём, доход шёл на содержание церкви. Позднее с западного фасада была выстроена часовня.
Довольно крупный храм выстроен в традициях архитектуры XVI века с элементами эклектики.
Постников и Савватеев не только выстроили церковь, но и приобрели иконы и утварь (практически все имущество старой церкви погибло в пожарах). За труды в восстановлении Гостинодворского храма Постников был награжден Орденом Святой Анны 3-й степени, а Савватеев — золотой медалью. В 1881 году умершего Федора Постникова отпевал в Гостинодворской церкви сам архиепископ Палладий (Раев).
В Николо-Гостинодворской церкви служил священником будущий митрополит Казанский и Свияжский, затем Патриарх Московский, герой освободительной борьбы в «смутное время» Ермоген, канонизированный в 1913 году. Он сам писал, что в 1579 году, когда была обретена чудотворная Казанская икона Божьей Матери, был «... в чину поповстве Святого Николы иже зовется Гостин».
Главной святыней Николо-Гостинодворской церкви, привлекавшей множество богомольцев, была икона святителя Николая, обретенная в 1777 году в развалинах одной из сожженных пугачевцами церквей. В 1830 году во время эпидемии холеры в домах, куда носили эту икону, не было умерших. В 1842 году считали, что именно эта икона спасла от пожара Николо-Низскую церковь.
В 1889-1906 гг. настоятелем храма был Афанасий Федорович Воскресенский (1848-1906), уроженец села Яндоба Ядринского уезда, выпускник Казанской духовной семинарии 1872 года.
В настоящее время в здании Гостинодворской церкви (адрес: ул. Кремлёвская, 2 / ул. Профсоюзная, 6) находится Главное архивное управление при Кабинете Министров Республики Татарстан.
