Excavaciones en el subsuelo de este edificio han revelado los cimientos de construcciones romanas y carolingias.

En la primera mitad del siglo XIII, se decidió reemplazar la catedral carolingia por un nuevo edificio, que sería un relicario de piedra para los huesos de los Reyes Magos, catedral imperial para respaldar el reclamo de los arzobispos de Colonia por ser los oficiantes de la coronación imperial. Desde el punto de vista del arzobispo Konrad von Hochstaden, consciente del poder, una coronación imperial solo era válida si la realizaba el arzobispo de Colonia. Además, la catedral, que las reliquias de los Reyes Magos convirtió en uno de los lugares centrales de peregrinación en la Edad Media, debería superar claramente a las iglesias románicas de Colonia.[1]​[2]​ El cabildo de la catedral decidió construir la catedral en el estilo gótico de las catedrales francesas y probablemente también se inspiró en la apariencia de la capilla del palacio parisino Sainte-Chapelle, que fue consagrada en 1248.

La construcción de la actual catedral empezó en 1248 y terminó en 1880. Hacia 1510 se interrumpió la construcción por problemas económicos y por falta de interés. En 1560, el cabildo de la catedral dejó de aportar fondos de forma definitiva. A partir de entonces, durante siglos se estuvo utilizando como templo la parte ya terminada.

La finalización de la catedral fue fuertemente apoyada en el siglo XIX por el emperador alemán, que reconocía en el gótico una herencia germánica. A la vez, hacía construir junto a la catedral la impresionante estación de tren, símbolo de la fusión del pasado y el futuro en la nueva Alemania. La historia, en detalle, es la siguiente. A comienzos del siglo XIX, los románticos alemanes, entusiasmados por la Edad Media, llamaron la atención sobre el estado en que se encontraba la catedral inconclusa. Personalidades como Joseph Görres y Sulpiz Boisserée impulsaron la terminación, de forma que consiguieron que el rey Federico Guillermo IV de Prusia destinara fondos a este proyecto. El 4 de septiembre de 1842 se puso la primera piedra para la renovación de la construcción, participando el propio rey y el coadjutor y futuro arzobispo de Colonia Johannes von Geissel. Poco antes se había fundado el Zentral-Dombau-Verein zu Köln (Asociación para la construcción de la catedral de Colonia) con el objetivo de conseguir fondos.

Finalmente, el 15 de octubre de 1880, la inauguración de la catedral no presentó la misma imagen de armonía, pues coincidió con el momento álgido del Kulturkampf, el desencuentro entre el Estado prusiano y la Iglesia católica en Alemania, por lo que en el momento de la inauguración el arzobispo de Colonia, Paulus Melchers, se encontraba en el exilio. Por eso, el cabildo de la catedral se negó a que se celebrara una misa de inauguración con presencia del emperador Guillermo I y solo permitió un solemne Te Deum.

En los bombardeos efectuados por los aliados durante la Segunda Guerra Mundial la catedral sufrió graves destrozos, aunque su estructura se mantuvo intacta: se dañó la base de la torre izquierda (que permaneció muchas décadas sin restaurar, siendo visible la estructura de ladrillo que se colocó inmediatamente después del daño) y, sobre todo, se destruyeron (por las vibraciones) muchos vitrales; otros pudieron ser retirados a tiempo. La única bomba que le afectó directamente fue la que causó los daños en la torre. La catedral contaba con un sistema de iluminación que advertía a los pilotos de los bombarderos. Pese a los destrozos, la estructura continuó dominando la silueta de la ciudad en ruinas. Son memorables las imágenes de la procesión del Corpus en 1946, por entre la ciudad en ruinas, hacia la catedral.

Desde hace muchos años, la catedral está sometida a un proceso continuo de reparación, pues la contaminación atmosférica y las palomas causan daños en la piedra. La catedral se construyó con tres tipos de piedra diferente; uno de ellos es bastante sensible a estas influencias. Otro de los tipos de piedra ennegrece considerablemente con el paso del tiempo.