Die sogenannte Gaukirche am Paderborner Domplatz, St. Ulrich, wurde um 1170/80 erbaut. In den Jahren 1231 bis 1810 gehörte St. Ulrich, ursprünglich auch St. Maria, zu einem Zisterzienserinnen-, ab 1505 zu einem Benediktinerinnenkloster. Mitte des 14. Jahrhunderts wurde die Ursulakapelle angebaut und um 1400 die Kreuzkapelle ergänzt.
1883-87 wurde die Gaukirche restauriert; im Zuge dessen entstand auch das Nordportal. Nach Zerstörung während des Zweiten Weltkriegs mussten die Dächer nach Kriegsende erneuert werden.

Die Basilika auf kreuzförmigem Grundriss von zwei Jochen Länge wurde im gebundenen System errichtet und schließt mit einem quadratischen Chor ab. Ungewöhnlich ist insbesondere der Eckturm über dem westlichen Joch.

An den schlichten Außenbau aus Bruch- und Werksteinen mit Rundbogenfenstern schließt sich im Westen eine Vorhalle an, die 1746-49 von Franz Christoph Nagel geschaffen wurde. Die geschwungene barocke Fassade der Vorhalle wurde auf der Marktseite in die Straßenfront eingefügt und teilt sich in zwei Geschosse, die mit Pilastern gegliedert sind. Unter dem Dreiecksgiebel steht die Figur des heiligen Ulrich in einer Nische. Nach oben hin wird die Fassade von einer Attika abgeschlossen.

In der Vorhalle befindet sich das romanische Portal, durch das die Basilika ursprünglich betreten wurde. Breite Gurtbögen auf massiven Pfeilern kennzeichnen das Langhaus von St. Ulrich. Das Kreuzgratgewölbe im Mittel- und Querschiff sowie im Chor ist annähernd kuppelförmig. Das südliche Seitenschiff wird von einer Längstonne bedeckt. Über dem nördlichen Seitenschiff wurde 1887 eine Empore errichtet.

Der Chor ist mit verblendeten Arkaden versehen. In der östlichen Bogenöffnung zum südlichen Seitenschiff befinden sich Reste einer romanischen Wandmalerei. Die farbigen Architekturfassungen wurden 1968 nach Befunden ergänzt.