Wykopaliska archeologiczne, które miały miejsce pod dzisiejszą świątynią i jej najbliższej okolicy w latach 1965/1966 i 1973–1979 poświadczają o istnieniu zabudowań z I wieku n.e. Położony wówczas na wyspie na wschód od pretorium sąsiadował z natatio-powszechnym w czasach rzymskich typem kąpieliska. W połowie II wieku znajdowały się tu cztery symetrycznie usytuowane trójnawowe hale tworzące od zachodu, południa i wschodu pierzeje czworobocznego placu. Prawdopodobnie pełniły funkcję handlową.

Pierwsze wzmianki o istniejącej tu świątyni pochodzą z przełomu VII i VIII wieku, przy czym przypuszcza się, iż klasztor z kaplicą istniał tu od V w. W X wieku powstał nowy kościół. Kartularz z Lorsch wspomina o założeniu przez arcybiskupa kolońskiego Bruna kościoła opackiego dedykowanego św. Marcinowi z Tours. Tenże hierarcha ofiarował w swoim testamencie relikwie św. Elifiusza z Rampillon, który stał się drugim patronem kościoła. W 989 arcybiskup Everger ofiarował kościół iroszkockim Benedyktynom, którzy władali kościołem i klasztorem do śmierci ostatniego opata Alvolda w 1103. Od 1056 roku mieszkał tu Marian Szkot, autor Kroniki Świata. Prawdopodobnie kościół był trójnawową bazyliką z parami wież od wschodu i zachodu. W 1150 roku wybuchł na przedmieściach Kolonii pożar, który dotknął także część centrum z kościołem i klasztorem. Arcybiskup koloński Filip I z Heinsbergu poświęcił w 1172 zachowaną do dziś część wschodnią zbudowaną w układzie treflowym (od południa, północy i wschodu przylegają do kwadratowego skrzyżowania naw trzy półkoliste absydy). Przy północnej absydzie dobudowano dwie kaplice, powstałe na miejscu zniszczonego przez pożar klasztoru. Opat Simon (1206–1211) i jego brat dokonali fundacji nowego klasztoru. W połowie XIII wieku zbudowano trójnawowy korpus nawowy, przebudowano część wschodnią, m.in. powiększono otwory okienne. Powyżej skrzyżowania naw wzniesiono potężną kwadratową wieżę z narożnymi oktagonalnymi wieżyczkami.

W 1378 roku pożar uszkodził dachy wież, natomiast wichura w 1434 spowodowała znaczniejsze uszkodzenia, w wyniku których runęła częściowo wieża i dachy, uszkadzając m.in. ołtarz główny. Dwa lata później w ramach odbudowy ufundowano upamiętniający to wydarzenie dzwon. Za rządów opatów Jakoba von Wachendorpa (1439–1454) i Adama Meyera (1454–1499) kościół otrzymał późnogotycki wystrój wnętrza. W 1509 roku powstał nowy ołtarz główny, z którego zachowało się do dziś kilka figur. Znaczną część średniowiecznego wyposażenia zastąpiono w XVII i XVIII w. barokowym. Inicjatorem barokizacji wystroju był m.in. opat Heinrich Obladen, który ufundował nowe organy. Opat Franz Spix przeprowadził szereg zmian w obrębie przestrzeni prezbiterialnej, wyburzając m.in. romańską kryptę. Pod koniec XVIII wieku ściany wnętrza pokryto malowidłami o formach klasycyzujących. W tym stylu powstał też stół ołtarzowy i ambona. W międzyczasie miała miejsce kolejna katastrofa, runęła północno-zachodnia wieżyczka uszkadzając dach. W październiku 1794 roku Kolonię zajęły wojska francuskie, które stacjonowały tu przez 20 lat. Podczas okupacji narzucono oświeceniowo-rewolucyjne idee mające na celu m.in. laicyzację miasta. W 1801 roku Kolonia straciła status arcybiskupstwa, a katedra stała się kościołem parafialnym, zniszczono kilkadziesiąt kościołów, kaplic i klasztorów. Zamieszkujący klasztor przy Wielkim Świętym Marcinie 21. mnichów musiało opuścić swoje miejsce. 11. z nich pozostało kapłanami w innych parafiach. W 1802 roku zburzono przykościelny klasztor, uszkodzeniom uległ także kościół. Po klęsce Napoleona i przemianach społeczno-kulturalnych nastąpił okres kontrofensywy prądów katolickich które znacznie przywróciły historyczny charakter miasta, zaś od 1843 roku miała miejsce restauracja Wielkiego Świętego Marcina. W 1875 kościół pokryto nowym dachem. Wnętrze kościoła odrestaurowano pod kierunkiem Augusta Essenweina, ściany otrzymały nowe malowidła o tematyce biblijnej. W takim stanie kościół przetrwał do II wojny światowej, kiedy to kościół był dwukrotnie niszczony, w 1942 i 1945. Runęły sklepienia, wieża i część murów lateralnych. Szczęśliwie ocalały znaczne fragmenty najstarszej części wschodniej. Plany odbudowy kościoła poprzedziła dysputa, w której postulowano pozostawienie ruin jako pomnika będącego znakiem przestrogi i upamiętniającego ofiary wojny. Ostatecznie wygrała koncepcja odbudowy kościoła, którą rozpoczęto w 1948 roku od prezbiterium (ukończone w 1954) następnie korpusu nawowego (1977), wieży (1965). W 1971 roku świątynię nakryto nowym dachem. W 1985 koloński arcybiskup Joseph Höffner poświęcił odbudowany kościół i sprowadził do jego wnętrza relikwie świętych Brygidy oraz Sebastiana i Engelberta z Kolonii.