Biskup Maciej Gołańczewski pomimo trwających konfliktów z zakonem nie porzucił swego zamiaru budowy nowej katedry we Włocławku. Przez kolejne lata gromadził fundusze i przygotowywał plany nowej świątyni w stylu gotyckim, wzorowanej na katedrach francuskich, znanych mu z podróży po zachodniej Europie.

Pierwszym krokiem do realizacji tych planów była wtórna lokacja miasta na prawie chełmińskim dokonana 8 września 1339 r. Pół roku później, gdy miasto zaczęło się dźwigać z ruin i na nowo zaludniać, rozpoczęto budowę katedry, jednakże zdecydowano się wznieść ją na nowym miejscu, na wzgórzu w oddaleniu od brzegu Wisły. Biskup Maciej Gołańczewski 25 marca 1340 r. poświęcił kamień węgielny, uroczyście rozpoczynając wznoszenie nowej katedry od prezbiterium i zakrystii południowej wraz ze skarbcem. Przez kolejne 25 lat mozolnie wznoszono mury włocławskiej katedry pod nadzorem biskupa Macieja, który 4 grudnia 1364 r. złożył urząd na ręce papieża Urbana V, jednocześnie prezentując swego bratanka Zbyluta jako następcę na stolicy biskupiej. Sam osiadł na zamku w Raciążku i tam zmarł 16 maja 1368 r. Pochowano go w zakrystii wznoszonej nowej katedry włocławskiej. Mogiłę tę odkryto podczas prac regotyzacyjnych w końcu XIX w.

Trudno dziś z całą pewnością ustalić, jak przebiegała budowa katedry włocławskiej. Zapewne jeszcze za rządów biskupa Macieja Gołańczewskiego zakończono budowę pierwszego etapu, czyli prezbiterium oraz zakrystii południowej i skarbca. Chór kapłański nowej katedry, zgodnie ze średniowieczną sztuką budowlaną, jest orientowany, czyli wzniesiony na osi wschód – zachód. Prezbiterium tworzą cztery przęsła na planie prostokąta, zamknięte od wschodu trójbocznie. Z zewnątrz prezbiterium opięte jest masywnymi szkarpami. Szkarpa pomiędzy trzecim a czwartym przęsłem została nadwieszona i połączona łukiem odciążającym ze szkarpą zakrystii. Zastosowanie tego typu szkarpy nawiązuje do francuskiego sytemu budowy świątyń gotyckich.

Do wnętrza katedry wchodziło się wówczas od strony miasta, czyli od północy, przez otwór wejściowy zamknięty łukiem odcinkowym w płytkiej ostrołukowej blendzie w północnej ścianie prezbiterium (obecnie wejście do zakrystii północnej). Od zachodu wejścia nie było ze względu na prace budowlane przy wznoszeniu korpusu nawowego. Maswerki ostrołukowych okien wykonano z wapienia. Zakrystia południowa i skarbiec dostępne były jedynie z prezbiterium. Możlie że w tym czasie brakowało jeszcze sklepień, które zgodnie z ówczesną sztuką budowlaną wznoszone były dopiero po zakończeniu wznoszenia dachu. We wnętrzu prezbiterium między oknami wmurowane zostały ceramiczne garnki akustyczne.

Dzieło rozpoczęte przez biskupa Macieja kontynuował jego następca – Zbylut Gołańczewski (1365–1383), dotychczasowy proboszcz włocławski. Za jego rządów w diecezji prawdopodobnie dokończono dachy chóru i zakrystii oraz ustawiono szafkowy ołtarz główny z figurą Matki Bożej. W tym czasie zbudowano także ściany trójnawowego korpusu oraz wieże, z których jedynie wieża północna sięgała gzymsu nawy głównej. Za takim stanem budowy katedry we Włocławku przemawia fakt ufundowania przez biskupa Zbyluta dzwonu. Całość budowli nakryto dachami wzniesionymi na masywnej drewnianej więźbie dachowej pokrytej ciężką dachówką mnich-mniszka, którą sprowadzono Wisłą z Gdańska lub z Nieszawy.

Rozpoczęta budowa katedry przebiegała już wówczas według zmienionych planów. Dobudowywany bazylikowy korpus katedry został uproszczony i pomniejszony, przez co sprowadzono go do założeń typowych dla świątyń parafialnych czy zakonnych. Nie wzniesiono nawy poprzecznej oddzielającej prezbiterium od korpusu nawowego. Główna nawa trójnawowego korpusu wzniesiona została jako węższa od prezbiterium, co jest wyjątkiem w kościołach katedralnych. Uproszczono także plan masywu zachodniego, rezygnując całkowicie z westwerku i wtapiając wieże w pierwsze przęsła naw bocznych. Trójnawowy, sześcioprzęsłowy korpus zbudowano w układzie bazylikowym na planie prostokąta, z niższymi i węższymi nawami bocznymi.

Przy budowie korpusu nawowego katedry we Włocławku zastosowano tak zwany „krakowski” system konstrukcyjny, w którym nie stosuje się nadwieszanych łuków odporowych przenoszących obciążenia sklepienia nad nawą główną na zewnętrzne przypory naw bocznych. Zbudowanie masywnych filarów międzynawowych pozwoliło na wzniesienie górnych partii ścian nawy głównej przy zastosowaniu cieńszych ścian magistralnych wzmocnionych konstrukcyjnie szkarpami, których podwalinę stanowią filary i rozpięte między nimi łuki arkad. Całość murów korpusu wzniesiona została z cegły palonej, ułożonej w wątek gotycki, na fundamencie z kamieni polnych. Do wnętrza korpusu prowadziły dwa ostrołukowe otwory wejściowe nieosłonięte kruchtami: wejście główne od zachodu, znajdujące się na osi nawy głównej, oraz wejście boczne od północy, od strony miasta, w czwartym od zachodu przęśle nawy bocznej.

Kolejni następcy biskupa Zbyluta Gołańczewskiego na włocławskiej stolicy biskupiej wiele wnieśli w dzieło budowy katedry włocławskiej. Trudno dziś dokładnie stwierdzić, jak przebiegały prace przy budowie i upiększaniu włocławskiej katedry. Postęp prac budowlanych był jednak na tyle duży, że w dniu 13 maja 1411 r. można było dokonać uroczystej konsekracji świątyni. Aktu poświęcenia katedry we Włocławku, jako wotum za zwycięstwo odniesione nad Krzyżakami pod Grunwaldem, przy obecności króla Władysława Jagiełły, dokonał wywodzący się z zakonu dominikanów biskup Jan, tytularny biskup taurisiensis, sufragan włocławski. Gdy konsekrowano katedrę, nie były jeszcze zakończone wszystkie prace budowlane. W jej wnętrzu nie było jeszcze wzniesionych sklepień w korpusie nawowym, zapewne nie było także posadzek oraz tynków, nie ukończono także budowy murów wież. Całość korpusu nawowego była już na pewno nakryta dachem.