Pierwszy, niewielki kościół powstał najprawdopodobniej w 1185 roku. 22 stycznia 1227 roku pomorski książę Świętopełk przekazał kościół zakonowi oo. dominikanów, których przyprowadził Jacek Odrowąż.

Budowę istniejącego obecnie kościoła rozpoczęto po 1348 roku, wznosząc w pierwszej fazie prezbiterium a następnie trzynawowy, halowy korpus zachodni, którego przypory zostały wciągnięte do środka. Równocześnie trwała rozbudowa klasztoru. W 1487 roku podwyższono wieżę o część ośmioboczną.

11 października 1587 roku w kościele św. Mikołaja miało miejsce wręczenie przybyłemu ze Szwecji królowi Zygmuntowi III aktu elekcji, po uprzednim (7 października) zaprzysiężeniu przez niego w kościele w Oliwie zobowiązań wobec Rzeczypospolitej, tzw. pacta conventa, uchwalonych przez Sejm. Był to moment, który rozpoczął okres świetności kościoła św. Mikołaja - w klasztorze zaczęło mieszkać więcej zakonników, kwitło życie intelektualne i kaznodziejstwo, a kościół otrzymał nowe wyposażenie (główny ołtarz, stalle, ambonę, organy).

W 1813 roku w skutek ostrzału rosyjskiego kościół doszczętnie spłonął. W 1834 roku nastąpiła kasata klasztoru a dominikanie byli zmuszeni do opuszczenia miasta. Zrujnowane zabudowania klasztorne ostatecznie wyburzono. Przy kościele powstała parafia katolicka.

W 1929 roku decyzją papieża Piusa XI kościół otrzymał tytuł Bazyliki Mniejszej.

W kwietniu 1945 roku, po 111 latach przerwy, dominikanie znowu pojawili się w Gdańsku i zamieszkali przy swoim dawnym kościele. Przybyli głównie ze Lwowa, po ponownym zajęciu tego miasta przez ZSRR. Przywieźli z tamtejszego kościoła dominikanów średniowieczną ikonę Matki Bożej Zwycięskiej, patronki tego miasta, która do dzisiaj znajduje się w kościele. Łaskami słynący obraz był ofiarowany zakonowi dominikanów w 1260 przez Konstancję, żonę Lwa - księcia halicko-włodzimierskiego.
W 2018 roku w kościelnej dzwonnicy odkryto uważane od II wojny światowej za zaginione fragmenty barokowego obrazu Matki Boskiej z Dzieciątkiem.