Die Anfänge der Gaukirche St. Ulrich liegen im Dunkeln. Nach späterer Überlieferung soll bereits bald nach der Gründung des Bistums und Erbauung der ersten Domkirche durch Bischof Badurad im 9. Jh. der Gottesdienst für das Volk von dem des Bischofs getrennt worden sein. Dazu wurde im Bereich der Dom-Immunität, in der die niedere und höhere Geistlichkeit wohnte und bis 1370 auch der Bischof residierte, südlich der Bischofskirche die Gaukirche (auch Gokirche, Gokerken oder lat. ecclesia rurens genannt) errichtet. Sie diente als Pfarrkirche für das Volk des Padergaues. Aus einer Urkunde von 1183 geht hervor, dass seitens des Domprobstes die Synodalsachen (Gerichtsangelegenheiten) in der Gaukirche verhandelt wurden und dem Pfarrer von St. Ulrich die "Leitung des Paderborner Volkes" anvertraut war.
Im Jahre 1229 wurde von dem Edelherrn Hermann v. Waldeck auf dem Grunde des Sternberger Hofes neben der Gaukirche ein Zisterzienserkloster gegründet. Die ersten Nonnen kamen aus Münster. 1231 wurde die Kirche mit allen Rechten und Einkünften dem Kloster inkorporiert und ein Jahr später auch vom Bischof Bernhard IV bestätigt. Der Konvent wählte seitdem den Pfarrer. Dieser war zugleich Probst des Klosters. Er musste sich vor Amtseintritt in der Ursulakappelle der Äbtissin eidlich verpflichten. Im gleichen Jahre 1231 wurde auch das Pfarrgebiet der Stadt Paderborn neu geordnet. Bis dahin war die Gaukirche einzige Pfarrkirche im Stadtbereich mit Ausnahme des Teils, den Bischof Meinwerk 1036 dem von ihm gegründeten Busdorfstift unterstellte. Wegen der zu sehr angewachsenen Seelenzahl wurde nun ein Teil an die Pfarrei des Niederen Chores des Domes, ein anderer an die Marktkirche übertragen. Auch das Verhältnis der Gaukirche zum Dom wurde festgelegt "wie es bisher üblich gewesen ist": Der Domprobst war der Patron der Kirche. Sie durfte an den Sonn- und Feiertagen kein Kreuz tragen, vielmehr mussten ihre Angehörigen und ihr Rektor an der Prozession des Domes teilnehmen. An den Hochfesten des Jahres mussten sie dem Gottesdienst in der Domkirche beiwohnen.

Über die genaue Entstehungszeit der Kirche wissen wir nichts, da jegliche urkundliche Überlieferung fehlt. Wahrscheinlich stand an dieser Stelle ein karolingischer oder ottonischer Vorgängerbau. Die heutige Kirche muss aus stillistischen Gründen in die Zeit 1170 bis 1180 datiert werden. Aus der Nachricht, dass 1183 Rechtssachen durch den Domprobst in der Gaukirche entschieden wurden, könnte gefolgert werden, dass das Kirchengebäude vor diesem Datum vollendet war. Im 14. Jahrhundert fügte man die Ursulakapelle im Süden und die Kreuzkapelle im Norden hinzu. Die stattliche Stiftung von 60 rheinischen Gulden erfolgte 1426 für die Ausbesserung des Turmes. Offenbar war damals der mächtige Glockenturm in schlechtem Zustand. Wann das nördliche Seitenschiff zur Halle erhöht wurde, ist nicht mehr auszumachen. Größere Veränderungen brachte das 18. Jh. Der kurfürstlich kölnische Architekt Franz Christoph Nagel (1699-1764), der für Kurfürst Clemens August in Paderborn arbeitete, fügte zwischen 1746 und 1749 an das wetsliche Hauptportal eine tonnengewölbte Vorhalle an und baute davor die schöne Barockfassade. 1787 schließlich trug man den spitzen, hohen Turmhelm ab und ersetzte ihn durch ein niedrigeres Haubendach. Von 1883 bis 1887 erfolgte die erste, nicht sehr glückliche Restaurierung und "Purifizierung" in historisierenden Formen und die Ausstattung mit neugotischem Mobiliar. In das hallenartige nördliche Seitenschiff baute man eine Empore für die Orgel ein. Anschließend wurde der Turmhelm in Anlehnung an seine ursprüngliche Gestalt wieder errichtet. Bei neuerlichen Restaurierungsarbeiten 1938 entfernte man die Zutaten des vorigen Jahrhunderts wieder und entdeckte unter der Tünche Reste der Bemalung des 13. Jh. 1944/45 erlitt die Kirche durch Fliegerbomben erhebliche Schäden. Der Wiederaufbau geschah seit 1947 und erstreckete sich über einen längeren Zeitraum. Dabei erhielt der Turm ein seinen Proportionen besser entsprechendes Zeltdach.

Der Grundriss der Gaukirche zeigt eine kreuzförmige Gewölbebasilika. An die quadratische Vierung schließen sich im Süden und Norden die Arme eines weit ausladenen Querhauses an, während sich nach Westen das Kirchenschiff öffnet. Im Osten mündet die Vierung in das kastenförmige Presbyterium mit geradem Chorschluss. Das nur aus zwei Jochen bestehende dreischiffige Langhaus ist im "gebundenen System" errichtet: Unter den quadratischen gewölbten Jochen des Mittelschiffs sind je zwei Arkadenöffnungen zusammengefasst. Während Mittelschiff, Vierung, Querhaus und Chor von kuppeligen Kreuzgratgewölben überspannt sind, hat das Seitenschiff eine Längstonne mit Stichkappen. Die massigen Pfeiler mit den rechteckigen Vorlagen und breiten Gurtbogen lassen darauf schließen, dass die Kirche von Anfang an als Gewölbebasilika geplant war. Die Pfeiler des ersten Langhausjoches sind stärker als die übrigen, da sie den achteckigen Turm zu tragen haben. Im Süden wurde zwischen Seitenschiff und Querhaus die quadratische Ursulakapelle angebaut. An der Nordseite ist zwischen Querhaus und Chor die ebenfalls quadratische Kreuzkapelle eingefügt. Die barocke Vorhalle mit der geschwungenen Fassade sitzt nicht ganz regelmäßig vor dem westlichen Hauptportal, da bei der Errichtung im 18. Jh. auf bestehende Häuser Rücksicht genommen werden musste.