Новый важный этап в истории строительства церкви св. Николая начинается, по-видимому, около 1408 г.. когда приступили к перестройке продольной части и хора. По данным источников, в 1423 г. производили работы по надстройке башни; из этого следует, что работы по реконструкции продольной части были закончены. К 1434 г. относятся сведения о пожертвовании денег для службы на алтаре Маргариты; следовательно, работы по реконструкции к этому году были полностью закончены, и, значит, пожар 1433 г. никакого ущерба Николаевской церкви не причинил. В результате реконструкции церковь св. Николая потеряла черты переходного стиля (исключением является лишь северный портал); она получила вид, характерный для построек таллинской школы XV в. При перестройке сохранилась большая часть южной и северной стен, так что ширина продольной части осталась прежней. Однако общий облик храма совершенно изменился. Судя по следам на южной, западной и северной сторонах, высота боковых была увеличена на 3 м, а средний неф был надстроен до высоты 22,8 м. Стена северного нефа была у третьей и четвертой травей (с запада) сломана, и здесь была сооружена небольшая пристройка, имеющая длину двух травей.

С северным нефом эта пристройка соединена двумя широкими арками. Вместо небольших двойных окон церковь получила высокие готические окна. Старый хор был полностью снесен и возведен новый обширный хор с деамбулаторнем. Была построена новая сакристия. В начале XV в. церковь получила также пристройки в виде капелл.

Уже в 1423 г. упоминается капелла Юргена. Она была пристроена с северной стороны ко второй (с запада) травее в виде притвора, так что северный портал оказался внутренним.