Den frühesten fassbaren Ausgangspunkt der Stiftskirche bildet die Burgkapelle König Heinrichs I., die sich am Ort des heutigen Bauwerks erhob. Vermutlich bereits dem heiligen Servatius geweiht, handelte es sich um eine Saalkirche mit östlich angefügter, kurzer, dreischiffiger Grabkapelle. Vor deren Petrusaltar wurde Heinrich I. im Jahr 936 beigesetzt.

Unmittelbar anschließend entstand hier die Kirche des von Königin Mathilde gegründeten Damenstifts. Der Bau zeigte sich als etwa 52 Meter langer und 10 Meter breiter Saal, dessen Mittelzone beidseits von rechteckigen Annexen mit Emporen begleitet wurde – eine frühe Vorform des späteren Querhauses. Aufgrund der topographischen Lage am steilen Südhang musste das westliche Schiff durch tonnengewölbte Stützbauten gesichert werden; unter dem südlichen Seitenschiff hat sich ein kurzer Abschnitt eines solchen gewölbten Ganges erhalten.

Mit der Überführung bedeutender Reliquien in den Jahren 962/64 erhielt die Kirche zusätzliche sakrale Bedeutung. In diesem Zusammenhang dürfte die sogenannte „Confessio“ entstanden sein, ein kleiner hufeisenförmiger Raum unterhalb des Altars. Die Bestattung Königin Mathildes im Jahr 968 neben ihrem Gemahl unterstreicht die herausragende Stellung des Ortes innerhalb der ottonischen Memorialkultur.
Unter Äbtissin Mathilde begann schließlich ein umfassender Neubau. Ein dreischiffiges Langhaus entstand, das 997 geweiht werden konnte. Gleichzeitig wurden Teile der heutigen Krypta angelegt, vermutlich zunächst als Unterbau einer Westempore. Im südlichen Seitenschiff wurde die bis heute erhaltene Kapelle St. Nikolai in vinculis integriert. Der westliche Abschluss ist nicht eindeutig überliefert, dürfte jedoch einem frühromanischen Westbau mit quadratischem Kern und flankierenden Treppentürmen entsprochen haben.

Mit der Beisetzung der Äbtissin Mathilde im Jahr 999 setzte sich die Nutzung als dynastische Grablege fort. Kurz darauf wurde die Krypta erweitert und vollendet; über ihr entstand ein neuer Chorraum, in dem vermutlich auch der Königssarg neu positioniert wurde. Eingriffe wie die Beseitigung der älteren „Confessio“ und die Neuanlage eines Altars zeigen die fortschreitende liturgische und bauliche Neuordnung. Mit der Weihe von 1021 waren Querhaus und Sanktuarium in ihren Grundzügen abgeschlossen.