Fondata nel 1034 dall'arcivescovo Bisanzio, eretta per volontà del suo successore Nicola e completata nel 1064 al tempo di Andrea II, la cattedrale era una basilica a tre navate divise da colonne antiche di reimpiego, sopraelevata di ben cinque metri rispetto al precedente Episcopio abbattuto. I resti di questo sono stati inglobati sotto il pavimento della cattedrale, poggiato su una struttura ancor oggi visibile corrispondente all'antica confessio.

Tra 1034 e 1066, protomagister della fabbrica è il primo grande scultore e architetto pugliese, Acceptus, autore delle cornici dei cinque portali, di vari capitelli ritrovati durante i restauri e di un ambone, commissionato da Andrea II e ricostruito con qualche licenza nel 1955. Le immagini di questa chiesa, dei primi arcivescovi, del clero e del popolo si riconoscono nelle illustrazioni di tre rotoli di pergamena: gli Exultet 1 e 2 e il Benedizionale, che nell'XI secolo venivano usati nelle cerimonie del Sabato Santo e sono oggi conservati nel Museo Diocesano.

Il nucleo principale superstite della fabbrica del Mille, è riconoscibile nell'ambiente sotterraneo (confessio), diviso in tre navate, coperto da volte a crociera e preceduto da un atrio o vestibolo coperto da crociere senza sottarchi; queste si addossano sulla parete trasversale che chiude il complesso a ovest e proseguono verso nord e sud formando un corridoio che in origine metteva tale ambiente in comunicazione con l'esterno. Sul succorpo si elevava la navata spartita dai colonnati, rimaneggiata nella successiva ricostruzione del XII secolo.