Die erste Kirche auf dem Domberg wurde um 850 erbaut. Sie war Teil der Burg, die den im Jahr 888 erstmals urkundlich erwähnten adeligen Babenberger Brüder Adalbert, Adalhard und Heinrich gehörte, welche das Volkfeld verwalteten. Sie sollten die Hauptakteure der sogenannten Babenberger Fehde werden. Walter Sage konnte bei seinen Grabungen im Dom von 1969 bis 1972 die Fundamente eines Kirchenbaues von rund 13 m Breite und 20 m Länge nachweisen. An dessen Ausrichtung sich auch die nachfolgenden Dome orientieren sollte.