Der Neubau erhob sich wohl über einen kleineren kirchlichen Vorgängerbau, von dem jedoch keine Reste überliefert sind. Nach Sennhauser (1982) handelte es sich bei der Haito-Kirche um einen Saalbau, der wahrscheinlich von zwei langen Seitenräumen flankiert wurde. Er erstreckte sich über die keltische Strassenlinie, welche die heutige Rittergasse mit der Augustinergasse verband. Zu beiden Seiten der Westfassade weisen abgerundete mächtige Fundamente auf je einen Turm hin. Zwei Säulenfundamente in der Mitte des Schiffes markieren eine Schrankenanlage, die den Laienraum vom Chor separierte. Von dem Altarziborium, das nach schriftlicher  berlieferung im Jahr 823/24 von Bischof Haito gestiftet wurde, ist nichts mehr erhalten. Eine eingezogene halbrunde Apsis könnte den Chorabschluss gebildet haben. Unter dem Altarraum lag eine Krypta, von der die beiden seitlichen Eingänge erhalten sind. Das Haito-Münster war zu seiner Zeit, zwar als traditioneller Saalbau jedoch mit Doppelturmfassade, ein aussergewöhnlicher Bau. Kurze Zeit später wurde dieser Kirche eine Aussenkrypta angefügt, deren Reste östlich des heutigen Chorhauptes unter dem Boden der Pfalz teilweise erhalten sind: Drei Stollen, die im Osten und Westen durch Quergänge verbundene sind, münden in drei Apsiden, in welchen jeweils ein Altar stand. Gemauerte Bänke entlang der Stollenwände weisen auf einen Andachtsraum hin. Unklar ist jedoch, an welchen Gebäudeteil im Osten diese Krypta anschloss, ob direkt an die Apsis der Kirche, die man sich in diesem Fall weiter östlich vorstellen muss, oder an einen dazwischen liegenden Gebäudeteil. Ein Verbindungsgang könnte in den südlich gelegenen Bischofskomplex geführt haben.