Katedrála stojí na místě starších staveb z doby kolem roku 500 a 650, u severní hradby tehdejšího římského města. Roku 873 byl vysvěcen „Starý dóm“ se dvojím chórem a dvěma příčnými loděmi na obou koncích lodi. Roku 1164 přivezl arcibiskup z Milána ostatky sv. Tří králů, dar císaře Fridricha Barbarossy, a do Kolína začaly přicházet proudy poutníků. Roku 1248 byla zahájena stavba současného chrámu podle vzoru katedrály v Amiens, ovšem s pěti místo se třemi loděmi. Roku 1311 byly osazeny vitráže v chóru o celkové ploše 1350 m2 a roku 1322 chór vysvěcen. Základy pro jižní stranu včetně věže byly hotovy kolem roku 1360, kolem roku 1375 vznikl portál sv. Petra a roku 1437 dosáhla jižní věž výšky 59 m, takže se do ní mohly zavěsit tři zvony. Po roce 1510 však stavební činnost ustávala, až úplně přestala.
V letech 1814 a 1816 byly v archivech v Darmstadtu a v Paříži objeveny původní plány západního průčelí, a tak byl roku 1842 položen nový základní kámen. Roku 1848 proběhly oslavy 600 výročí založení a roku 1855 bylo dokončeno jižní průčelí. 1863 byla dokončena loď, stržena provizorní přepážka chóru a 1880 bylo dokončeno i západní průčelí s oběma věžemi. Slavnostního otevření se zúčastnil i císař Vilém I. Pruský, takže slavnost dostala spíš politický a národní význam. Právě totiž probíhal církevní boj (Kulturkampf), katolický arcibiskup byl ve vyhnanství a kanovníci i mnoho měšťanů se slavnosti nezúčastnilo.
