Von 1949 bis 1956 führte Baurat Dr. Bernhard Ortmann umfangreiche Ausgrabungen in der und rund um die Abdinghofkirche durch. Dabei stieß er unter anderem auf eine ältere kleine Saalkirche unter dem heutigen Mittelschiff. Der dann folgende Kirchenbau besaß im Osten eine Umgangskrypta und im Westen ein weit über die Wände des Langhauses ausladendes Querhaus sowie eine westliche Apsis. Der Archäologe Uwe Lobbedey vermutet hierin den ersten von Meinwerk errichteten Kirchenbau. Dieser stürzte laut Vita Meinwerci noch vor der geplanten Weihe Weihnachten 1022 ein, so dass nur die Krypta am 2. Januar 1023 in Anwesenheit Kaiser Heinrichs II. geweiht werden konnte. Für die Fertigstellung der Kirche wurde nach dieser Überlegung auf das westliche Querhaus verzichtet. Die Weihe erfolgte am 2. November 1031. Das Langhaus dieser dreischiffigen Klosterkirche stimmt weitgehend mit dem heutigen Bestand überein.

Der Stadtbrand 1058 war vermutlich der Anlass, den Westchor durch einen Westbau in der heutigen Form zu ersetzen und unter Verkürzung des Langhauses etwas weiter nach Osten zu verlegen (Weihe 1078). Gleichzeitig erhielten der Ostchor und die Krypta einen rechteckigen Abschluss, im Osten wurde ein Querhaus eingefügt. Nach dem Brand von 1165 wurde wiederum der Ostchor erneuert, das Querhaus aufgegeben und die gesamte Kirche eingewölbt. Ebenfalls der zweiten Hälfte des 12. Jh. entstammen "Abtskapelle" und Kreuzgang. Abgesehen vom Einbau gotischer Fenster blieb die Basilika nun jahrhundertelang in ihrem Bestand unverändert. Über die Ausmalung des Inneren ist bisher nichts bekannt, in der "Abtskapelle" befand sich noch 1945 eine spätromanische Darstellung der Krönung Marias.
Nach der Säkularisation und der zeitweiligen Wiederverwendung als preußische Garnisionskirche verfiel die Kirche in den Jahren 1806 bis 1866 zusehends. Der nördliche Treppenturm und die Turmobergeschosse stürzten ein, die Mittelschiffgewölbe mussten abgebrochen werden.
Nach der Übereignung an die evangelische Gemeinde 1866 wurden die verbliebenen Mauern gesichert, das nördliche Seitenschiff, die Mauern des Obergadens im neuromanischen Stil und die Obergschosse der Türme mit Spitzhelmen neu errichtet. Dabei verzichtete man auf eine Wiederherstellung der  Mittelschiffgewölbe zugunsten einer flachen Holzdecke (Baumeister W. Schulz aus Hannover). Nach den Entwürfen des Kölner Malers Michael Welter wurden die Decke mit dem apostolischen Glaubensbekenntnis, Chorwand und Triumphbogen mit figürlichen und ornamentalen Malereien geschmückt. Am 25. April 1871 wurde die Abdinghofkirche erneut geweiht.
Für die weitere Ausgestaltung wurde Prof. Ernst Pfannschmidt aus Berlin gewonnen. Von 1915-1919 malte er im Mittelschiff sechs Wandbilder: Den drei alttestamentlichen Bildern der Südseite (Mose empfängt die Gesetzestafeln, Die eherne Schlange, Mose schlägt Wasser aus dem Felsen) wurden drei Szenen des Neuen Testaments gegenüber gestellt (Geburt Jesu, Heilungen Jesu, Das Abendmahl).
Auf dem Triumphbogen waren Visionen aus der Offenbarung Johannes zu sehen. An höchster Stelle thronte der wiederkommende Christus. Seitenschiffe, Pfeiler und Arkaden wurden mit einer ornamentalen Ausmalung geschmückt. In  den Jahren 1925-1927 konnte Prof. Pfannschmidt die Gesamtgestaltung der Abdinghofkirche durch die Ausmalung des Chorraumes mit der Leidensgeschichte vollenden. Zugunsten einer Darstellung der Kreuzigung an der Ostwand wurde das Altarkreuz von 1871 aus dem Chorraum entfernt und erst 1961 wieder dort aufgerichtet. Durch die Bombenangriffe auf Paderborn am 22. und 27. März 1945 wurde die Abdinghofkirche stark zerstört. Auf eine Restaurierung der Wandmalereien wurde verzichtet, zumal die dafür notwendigen Gelder fehlten. Beim Wiederaufbau bis 1952 versah man die Kirche mit einem weißen Verputz. Dieser sollte die Klarheit der romanischen Architektur wieder zum Vorschein bringen.

Die Außenerscheinung der Basilika wird vor allem durch die Veränderungen anlässlich der Restaurierung 1866-1871 bestimmt. Damals wurde das helle Kalksteinmauerwerk durch die Abnahme des jahrhundertelang vorhandenen Verputzes freigelegt. Die Fensteröffnungen der neu aufgerichteten Wände des Obergadens und des nördlichen Seitenschiffes erhielten im Vergleich zu den mittelalterlichen Fenstern vergrößerte Öffnungen. Völlig neu waren die Rundfenster im Chor. Das südliche Seitenschiff zeigt fünf alte gotische Spitzbogenfenster von 1667 neben vier neuromanischen des 19. Jh. Die Westfassade ist oberhalb des durchlaufenden Gesimses ebenfalls rekonstruiert worden. Anstelle der im Zweiten Weltkrieg zerstörten Spitzhelme aus dem 19. Jh. erhielten die Türme Satteldächer. Nicht wieder aufgebaut wurde allerdings die Westapsis, da man einen axialen Haupteingang wünschte. Bogen und Ansatz dieser Apsis zeichnen sich im Mauerwerk deutlich ab.

Innenraum. Beim Betreten der Kirche durch das Hauptportal befindet sich der Besucher unmittelbar im tonnengewölbten Westchor, der gegenüber dem Langhaus deutlich erhöht ist. An ihn schließen sich in den Türmen Seitenräume mit Quertonnen an. Darüber liegt jeweils ein weiterer gewölbter Nebenraum (vermutlich Schatzkammer und Archiv) und wiederum ein Geschoss darüber eine Empore, die sog. "Kaiserloge", die sich durch den ganzen Westbau erstreckt. Ursprünglich war sie zum Mittelschiff hin offen. Zwischen 1871 und 1945 diente sie als Orgelempore. Von den beiden Treppentürmen, die zu diesen Räumen führten, ist nur der südliche erhalten.
Beim Eintritt in das dreischiffige Langhaus beeindrucken die großzügigen Proportionen des Mittelschiffes. Jeweils acht längsrechteckige Pfeiler der Arkaden tragen die Hochschiffwände, die durch ein umlaufendes Gesims und die Fensteröffnungen gegliedert werden. Die vier schlankeren Pfeiler der östlichen Arkaden wurden nach der Aufgabe des östlichen Querhauses eingefügt. Seit den Restaurierungen 1866-1871 ist das Mittelschiff wieder mit einer für die meinwerksche Zeit typischen Holzdecke versehen, so dass sich dem Betrachter weitestgehend der ursprüngliche Eindruck bietet. Der Triumphbogen öffnet den Blick in den rechteckigen Chorraum, der durch die darunter liegende gewölbte Krypta deutlich erhöht ist. Blendnischen gliedern den unteren Teil der Wände. Unter dem Triumphbogen hängt das neuromanische Altarkreuz, eine Stiftung von 1871.
Von den beiden Seitenschiffen hat nur noch das südliche seinen mittelalterlichen Bestand bewahrt. Die beiderseits vorspringenden rechteckigen Wandvorlagen tragen ein Kreuzgratgewölbe. Über der Tür zur Sakristei ist ein barocker Wappenstein aus den kriegszerstörten Klostergebäuden eingemauert. Er zeigt Attribute der beiden Kirchenpatrone, den Schlüssel des hl. Petrus und das Schwert des hl. Paulus, die sich unter dem Abtsstab kreuzen. Das nach 1866 neu ausgeführte nördliche Seitenschiff wurde ebenfalls mit Kreuzgratgewölben zwischen Gurtbögen versehen. Am östlichen Ende befindet sich die 1951 eingerichtete Taufkapelle mit Taufstein und Taufsymbolik.
Die Orgel wurde 1961 von der Firma Hammer aus Hannover erbaut. Das Instrument umfasst 34 Register mit etwa 2500 Pfeifen, die auf drei Manuale und ein Pedal verteilt sind. Das Pedal ist aus optischen Gründen in zwei Pedaltürme aufgeteilt. Der Orgelprospekt nach einem Entwurf von Architekt Wulf Knipping, Hagen, ist in einer Triptychon-Form, einem dreiteiligen Flügelaltar ähnlich, ausgeführt worden. Die Orgel erweist sich mit ihrer Disposition und Klangbreite als ein der alten Klosterkirche angemessenes Instrument, das vielseitigen Ansprüchen gerecht wird.
Von den ursprünglichen Ausstattungsstücken befindet sich der romanische Tragaltar (um 1115) des Rogerus von Helmarshausen, einem der bedeutensten Goldschmiede des hohen  Mittelalters, im Diözesanmuseum. Der auf vier Löwenpranken ruhende Altar aus Eichenholz ist mit vergoldeten Kupferplatten beschlagen und mit Szenen aus dem Leben und den Martyrien der Kirchenpatrone Petrus und Paulus sowie der hl. Blasius und Felix gestaltet. 

Aus den Seitenschiffen führen Treppen hinab in die 1023 geweihte Krypta, die sich unterhalb des Chores erstreckt. Sie ist als dreischiffige Halle mit Tonnengewölben gebaut, die so stark sind, dass sie 1945 der Luftmine standhielten.
Die drei Schiffe der Hallenkrypta werden von drei Vierpasssäulen an der Südseite, zwei Vierpasssäulen und einem (Ersatz-) Pfeiler aus dem Mittelalter an der Nordseite und Rechteckpfeilern im Westen gegliedert. Der Sarkophag Bischof Meinwerks hat in der Nische der Westwand gestanden. Die Mauerblöcke in den östlichen Ecken wurden erst nach 1165 als Verstärkung für den nun gewölbten Chorraum eingefügt. Das Gewölbe der Krypta wird von den Vierpasspfeilern getragen, deren Kapitelle z.T. reich verziert sind. Die bemerkenswerten Bündelpfeiler und Kapitelle sind wahrscheinlich aus der Meinwerk-Krypta übernommen und durch die übrigen Pfeiler ergänzt worden. Zwei der Kapitelle zeigen sehr fein ausgearbeitete Ornamente mit akanthusartigen Pflanzenformen. Das östliche Kapitell verfügt über den reichsten Schmuck. Das Tierkapitell zeigt acht Drachen mit geringeltem Hinterleib, Flügeln und einem kleinen Spitzbart am Kopf. Diese mythischen Drachen waren seit der Antike bis ins hohe Mittelalter Sinnbild für Naturkräfte, die hier vermutlich die Wasserquellen der Pader schützen sollten. Diese Schlangendrachen sind hier eine kunstgeschichtliche Kostbarkeit.

Beim Aufstieg zur Westwerkempore gelangt man zur seitlich liegenden sog. "Abtskapelle", die, im 12. Jh. erbaut, Kirche und Kloster miteinander verband. Sie gehört zu den schönsten Kapellen der westfälischen Spätromanik. Im fast quadratischen Raum befindet sich ein Steinfußboden mit Kreuzmuster. In der Mitte steht eine sehr schöne romanische Säule. Das Kapitell ist schlicht und ziemlich flach, rundum mit vier Reihen von Palmetten (fächerförmiges Blattornament) geschmückt. Unter dem Kämpfer befinden sich ein Schachbrett- und ein Flechtbandmuster. Ausgehend von der Säule entfalten sich in in vier Richtungen Kreuzgratgewölbe, die dem Kreuzmuster im Fußboden entsprechen. Die Kreuzgratgewölbe enden auf vier kleinen Dreiviertelsäulen in den Ecken. Diese sind mit Palmettenblättern geschmückt.