Ok. 235, dwaj żołnierze stacjonujący w Castra Bonnensia, Kasjusz i Florencjusz, zostali zamordowani za przyjęcie wiary chrześcijańskiej. Według tradycji, w IV wieku Święta Helena matka Konstantyna Wielkiego ofiarowała kaplicę w miejscu pochówku obu męczenników. Na ten temat nie ma potwierdzeń źródłowych, ale w wyniku badań archeologicznych potwierdzono istnienie starorzymskiej bazyliki i nekropolii z czasów konstantyńskich. Była to świątynia niewielka – długa na 13,70 m i szeroka na 8,80 m o jednej nawie. Świątynia była kilkakrotnie rozbudowywana w VII – IX w.
Około 1050 zburzono kościół, i na jego miejscu rozpoczęto budowę obecnej świątyni w stylu romańskim. Powstawał on w kilku etapach, przez dwa kolejne stulecia. W 1166 ukończono budowę wschodniego chóru zamkniętego półokrągłą absydą, który flankują dwie wieże. Transept, korpus nawowy oraz chór zachodni budowano do 1224. Na skrzyżowaniu naw powstała wieża na planie oktogonu. Inwestycja ta jest ściśle związana z przeniesieniem siedziby arcybiskupstwa kolońskiego do Bonn. Władza w Kolonii, od wieków miasta biskupiego została przejęta przez mieszczaństwo, która stała się Wolnym Miastem Rzeszy. W celu zachowania własnej suwerenności siedziba arcybiskupa była przeniesiona do sąsiedniego Bonn.