Abgesehen von der genannten Legende um den toten Kölner Bischof Maternus, der hier im 2. Jh. angelandet sei, weswegen die Kölner an diesem Felsvorsprung über dem Rhein ihm zu Ehren eine Kapelle bauten, gibt es eine weitere Legende, die dem Kölner Bischof Severin, der Ende des 4. Jh. lebte, die Errichtung dieser Kapelle für seinen Vorgänger Maternus zuschreibt. Zusätzlich ist es fraglich, ob die im Mauerverband der bestehenden Kirche gefundenen Grabplatten mit Kreuzen des 7./8. Jh. von einem lokalen Friedhof stammen oder als Baumaterial anderswoher beschafft wurden.
Vermutlich wurde (Alt-) St. Maternus, auch liebevoll Rodenkirchner Kapellchen genannt, im 10. Jh. als kleine Saalkirche mit halbrunder Apsis und eingestelltem Turm errichtet und erhielt im 15. Jh. ein südliches Seitenschiff und gotisch veränderte Fenster in der Nordwand.
Zu dieser Zeit erneuerte man auch die Apsis auf den alten Fundamenten. Das 17. Jh. fügte vor dem Turm und dem Seitenschiff einen Westbau und eine dieses Seitenschiff östlich baulich fortsetzende Sakristei an.
Hochwassermarken von 1784 und 1926 weisen auf die stete Gefährdung durch den Rhein hin. Die Weihe von (Neu-) St. Maternus 1867 beendete zunächst die Nutzung der alten Kirche, die mit einer Restaurierung 1925–1927 vor dem endgültigen Verfall gerettet wurde. Die schweren Beschädigungen im Zweiten Weltkrieg konnten erst bis 1954 behoben werden. Damals entstanden auch die Farbfenster von Conrad Schmidt. Die Figuren der vier Evangelisten in der Apsis stammen von der Kanzel(um 1880), ehemals in (Neu-) St. Maternus. Die Skulptur des hl. Maternus an der Außenseite der Apsis schuf Stefan Kaiser 1986.