Der Heinrichsdom war eine kreuzförmige Basilika mit dem Hauptchor im Westen und einem zweiten Chor im Osten, darunter liegenden Krypten und zwei Fassadentürmen im Osten. Er war 75 Meter lang, die Apsiden der Chöre besaßen eine Einwölbung, das Langhaus war mit einer flachen Holzdecke geschlossen.
Am Karfreitag, 3. April 1081, brannte der Dom völlig aus. Die kostbare Ausstattung der Kathedrale wurde zerstört. Die Beschädigung des Kirchengebäudes dürfte sich in Grenzen gehalten haben. Seine Instandsetzung erfolgte rasch und binnen weniger Jahre. In der Regierungszeit des Hl. Bischofs Otto I. von Bamberg (1102-1139) erhielt der Dom abermals eine prachtvolle Ausstattung. Die brandgeschädigten Fußböden erhielten einen neuen Belag, die Säulen wurden mit Stuck verkleidet und das ganze Kirchengebäude wurde durch neue Malereien verziert. Reste des Heinrichsdoms befinden sich heute noch unterhalb des Westchores.