Pierwszy obiekt sakralny w miejscu dzisiejszego kościoła św. Katarzyny mógł powstać, jak przypuszcza znawca historii Gdańska Andrzej Januszajtis, już w 997 roku i mieć związek z początkami chrześcijaństwa na ziemiach polskich i działalnością św. Wojciecha. Podbudową tej hipotezy jest odkrycie profesora Andrzeja Zbierskiego, który w 1986 roku odkrył miejsce pochówku z X wieku, gdzie szkielety zostały umieszczone w trumnach sporządzonych z wydłubanych pni drzew.
Drugi kościół w tym samym miejscu miał powstać, jak głosi tradycja, w 1185 roku przez Namiestnika Pomorza Gdańskiego, księcia Subisława. Natomiast Willi Drost, specjalizujący się w problematyce dotyczącej przeszłości kościoła św. Katarzyny zakłada, że świątynia powstała w latach 1230-1240 jako bazylika, z nawą główną wyższą niż boczne i zaopatrzoną w okna powyżej dachów bocznych naw.
Jeśli chodzi o samo powstanie murów, nie ma dowodów na jednoznaczną datę początkową, stąd różne hipotezy. Pewne jest, że w 1227 roku świątynia już istniała, gdyż znane jest imię księdza, który kościół objął. Był to książęcy kapelan Wilhelm. Z tą datą wielu historyków łączy powstanie parafii przy kościele.
Wieki XIII i XIV przyniosły kilka wzmianek historycznych na temat kościoła, takich jak w 1236 roku podanie wezwania „św. Katarzyna”, która z resztą została w 1271 roku obwołana patronką miasta Gdańska oraz bardzo lakoniczny zapis o świątyni roku 1298. Najczęstsze wzmianki w annałach miejskich związane są z obejmowaniem parafii przez poszczególnych kapłanów. Byli to: Luder (wzmiankowany w latach 1279, 1282 i 1283), Wisław (lata 1289 – 1295), Czesław (1308 rok), Henryk (1327 rok) oraz Burhardt (wzmiankowany w 1363 roku).
Historycy nie są pewni, czy w chwili powstania świątynia była jeszcze drewniana czy już murowana, za to dzięki szczegółowym badaniom archeologicznym wykonanym w 1956 roku wiadomo, że fundamenty kościoła św Katarzyny pochodzą z XIII wieku. Dodatkowo, dzięki odnalezieniu pod fundamentami licznych fragmentów dużych naczyń gospodarczych, oraz śladach targu w okolicy, potwierdzono kupiecki charakter terenu, na którym znajduje się świątynia.
Liczne badania historyczne i archeologiczne murów kościelnych oraz terenu do nich przylegającego, pozwoliły uznać świątynię za obiekt XIII wieczny położony na skraju ówczesnego miasta.
