Auf einem vor der Stadtmauer gelegenen Gräberfeld entstand in der 2. Hälfte des 4. Jh. eine Totenge-dächtnis-Kapelle, die Bischof Gregor von Tours im Jahre 590 als „ad sanctos aureos", d.h. „zu den goldenen Heiligen" bezeichnete, da sie mit Heiligendarstellungen in Mosaiktechnik ausge-schmückt war.

Die abgebildeten Heiligen wurden bald darauf mit dem römischen Soldaten und Kölner Stadtpatron Gereon in Verbindung gebracht, der in Köln das Martyrium erlitten hatte. Von 1067 bis 1069 entstand ein neuer Langchor mit zwei Flankentürmen und einer dreischiffigen Krypta. Zwischen 1151 und 1156 erweiterte man den Langchor um einen turmflankierten Etagenchor. 1219 bis 1227 erhielt der spätantiken Ovalbau einen steinernen Mantel, wodurch dieser zum Dekagon (= Zehneck) wurde. 

Die Bauzeit der Taufkapelle
liegt zwischen 1242 und 1245; 
die Sakristei entstand zwischen 1315 und 1319.

Im Zweiten Weltkrieg wurde die Kirche schwer beschädigt. Die vollständige Wiederherstellung dauerte bis 1984.
Das Innere des Dekagons ist ein vertikal betonter Zentralraum mit einer Scheitelhöhe von 34,55 Metern, der von einer Kuppel mit 21 Metern Spannweite überfangen wird. Das Dekagon ist damit der bedeutendste Kuppelbau zwischen der Hagia Sophia und dem Dom von Florenz. 

Die Farbfenster stammen von Georg Meistermann und Wilhelm Buschulte aus dem Jahr 1981. 
Der Langchor liegt deutlich höher als das Dekagon und ist über eine Treppenanlage zu erreichen. 
Die nur noch schemenhaft erhaltene Wandmalereien der Apsis entstanden in der 2. Hälfte des 12. Jh.
und zeigen im Zentrum Christus als Weltenherrscher.