Kościół św. Mikołaja zaczął powstawać wraz z miastem. Jego początki odnotowano w akcie lokacyjnym 10 kwietnia 1246 r., a pierwszy etap budowy zakończono w 1284 r. Dlaczego patronem został święty Mikołaj? Bo jest on patronem kupców i żeglarzy, a tych w ówczesnym Elblągu nie brakowało. Pierwszym proboszczem świątyni był niejaki Gotfryd, którego powołał na tę funkcję biskup Chrystian.
Jedyny katolicki kościół Początkowo kościół był niską halową budowlą, do której od strony zachodniej dostawiono wieżę. W połowie XIV w. podniesiono nawę główną, w latach 1380-1430 podniesiono nawy boczne. Jednocześnie do wieży dostawiono dwie boczne, które wzmocniły ją, bo groziła zawaleniem. Kościół przypominał wówczas bazylikę.
Po 1454 r i inkorporacji Elbląga do państwa polskiego, a następnie po reformacji, świątynia pozostała jedynym kościołem katolickim w Elblągu, patronat nad kościołem obejmują każdorazowo królowie polscy. Jednak wbrew umowom, w 1573 r. kościół przejęli protestanci. Po restrykcjach ze strony polskiego króla Zygmunta III jak i dyplomatycznych zabiegach Stefana Sadorskiego (przyczynił on się do powstania również obecnego sanktuarium Święta Lipka) kościół powrócił pod zwierzchność katolików.
Wielki pożar 26 kwietnia 1777 r. uderzenie pioruna w wieżę kościoła spowodował pożar i zniszczenie kościoła oraz sąsiedniego ratusza. W świątyni runęły sklepienia i zawaliła się wieża. Udało się uratować wiele cennych przedmiotów, wiele uległo jednak zniszczeniu. Ocalała chrzcielnica z brązu z 1387 r., dzieło mistrza Bernhusera, zniszczeniu uległa jedynie jej pokrywa.
Kościół odbudowywano wiele lat, obniżono jego wysokość o 7 metrów, wykonano drewniane sklepienie, a dach wykonano jako jednokalenicowy z sygnaturką. Samą wieżę odbudowano dopiero w 1907 r., wznosząc ją na wysokość 97 metrów, a dokonała tego elbląska firma budowlana należąca do Otto Depmeiera.
Ciekawostką jest to, że 9 listopada 1831 r. gen. Rybiński, internowany wraz z innymi żołnierzami polskimi uczestnikami Powstania Listopadowego, zamówił w kościele św. Mikołaja uroczyste nabożeństwo dla uczczenia poległych w tym powstaniu.
Katedra od 1992 roku
Świątyni ponownie została zrujnowana podczas walk o Elbląg w styczniu i lutym 1945 r . Zawaliły się stropy, a z wieży pozostał tylko wewnętrzny metalowy szkielet. Do odbudowy przystąpiono w 1948 r. O ogromie zniszczeń świątyni może świadczyć, że z jej wnętrza wywieziono 7 tysięcy metrów sześciennych gruzu. Przy odgruzowaniu pracowali społecznie mieszkańcy, w tym uczniowie, a także młodzież ze Służby Polsce. Strop odbudowanej świątyni wykonano z betonu, a dach wykonano jako trójkalenicowy. Kościół otrzymał dzwony z dawnego kościoła św. Anny. Nadmienić tu należy, że jeszcze w czasie I wojny światowej stracił brązowe dzwony skonfiskowane przez władze pruskie na cele przemysłu zbrojeniowego.
Obecnie na wyposażeniu kościoła św. Mikołaja, który w 1992 r. podniesiono do godności katedry nowo utworzonej Diecezji Elbląskiej znajdują się: wspomniana chrzcielnica z 1387 r., Grupa Ukrzyżowania oraz figury 12 apostołów z XIV w. ufundowane przez proboszcza Mikołaja Wulsacka. Proboszcz ten założył też pierwszą szkołę w Elblągu oraz bibliotekę.
W świątyni znajduje się szereg ołtarzy pochodzących z innych kościołów naszego miasta. Relikwia Krzyża Świętego pochodząca z dawnej kaplicy zamkowej, a ofiarowana jej w 1237 r. przez Wielkiego Mistrza Herman von Salza.
Przed katedra, po jej zachodniej stronie, w czerwcu 2001 r. odsłonięto pomnik Jana Pawła II na pamiątkę wizyty w Elblągu. Jest to dzieło Wawrzyńca Sampa.
