Деревянная Никольская церковь существовала уже в середине XVII в. В XVIII в. она была заменена каменной, рядом построена деревянная теплая Богоявленская церковь. К началу XIX в. оба храма обветшали, и в 1808-1818 гг. вместо них на средства прихожан был построен однопрестольный каменный храм. В 1848-1852 гг. он был перестроен на средства купца Алексея Ивановича Стахеева под наблюдением инженера Олехновича. Храм стал двухэтажным и трехпрестольным. Наверху был главный Никольский престол, внизу - теплые приделы.

Крупный храм нетрадиционной композиции. Он не имеет выступающей апсиды и по композиционному решению напоминает гражданское строение. Памятник архитектуры в стиле строгого классицизма.

Как и другие храмы Елабуги, Никольская церковь была очень богато убрана за счет прихожан - богатых купцов. В 70-е гг. XIX в. в ее росписи принимал участие знаменитый художник Василий Васильевич Верещагин (1842-1904), значительная часть этой росписи сохранилась. В Никольской церкви хранилась икона Святителя и Чудотворца Николая, обретенная в местности Святая Чаша близ Мамадыша в первой половине XVIII в. С ней ежегодно совершались крестные ходы в Мамадыш, собиравшие большое количество богомольцев.

Причт Никольской церкви не получал жалованья, но безбедно существовал за счет доходов от треб, заказных молебнов перед иконой Святого Николая и процентов с капитала (в начале XX в. - более 20000 рублей). Семьи причта жили в доме, построенном в середине XIX в. (ул. Гоголя, 6).

В 1814-1844 гг. настоятелем храма был протоиерей Максим Иванович Замятнин (1764-1844), выпускник Казанской духовной семинарии, который пользовался большой популярностью в городе, славился честностью, аскетизмом и благотворительностью.