Eine erste Kirche wurde wahrscheinlich im Zuge der Ortsgründung kurz nach 836 errichtet. Anfangs war die Kirche aus Holz, erst nach 1000 erbauten sich die Arzheimer eine steinerne Kirche, deren Turm noch heute steht. Um 1440-1446 erfolgte ein Neubau des Gotteshauses durch Hermann V. von Helfenstein und seine Ehefrau Anna von Boos von Waldeck. Im Gewölbe des Chores sind die Wappen der Bauherren als Schlusssteine eingesetzt. 1668 werden Arbeiten am Chor erwähnt, 1732-1772 Ausbesserungsarbeiten, darunter die des Jahres 1762, in dem das Kirchenschiff fertiggestellt wurde. Die alte Kirche wurde 1900/01 nach Plänen von Prof. Kleesattel umgebaut. Es entstand der heutige dreischiffige Erweiterungsbau zwischen Westturm und Chor. Bemerkenswert ist die Steinfigur der Hl. Aldegundis, der Patronin der Pfarrkirche. Sie wird als Äbtissin mit Hirtenstab und Evangelienbuch in den Händen dargestellt. Chr. von Stramberg erwähnt im "Rheinischen Antiquarius" (II,2 S. 419) ein zweites Bild der Hl. Aldegundis, das über dem Taufbrunnen angebracht gewesen sein soll. Die Steinfigur der Aldegundis befindet sich heute in der Kirche, nachdem sie lange Zeit ihren Platz außen am Chorstrebepfeiler der Kirche hatte.