Дата постройки последнего здания: сер. XIX в.   см. фотографии объектов той же эпохи

Первая деревянная Никольская церковь построена в морских кварталах Таганрога в 1777-1778. Основной объём — одноглавый восьмерик на четверике. В сер. XIX в. пристроены кирпичная колокольня с Пятницким приделом и трапезная в классическом стиле. В 1945 сгорел деревянный основной объём, в конце 1950-х взорваны и разобраны верхние ярусы колокольни, церковь закрыта, здание использовалось как склад. Сохранился первый ярус колокольни, трапезная, фундамент основного объёма. В 1990-х в процессе реставрации вновь выстроены колокольня и кирпичные восьмерик на четверике в старых формах, в 1993 возвращена верующим.

В церкви хранятся мощи местночтимого святого блаженного Павла Таганрогского (причислен к лику святых в 1999).