Un'indicazione particolarmente importante proviene dal rinvenimento dei resti delle fondazioni delle strutture isolate che dividevano la navata centrale dalle laterali. Si tratta di blocchi di muratura delle dimensioni di m. 1,25 x2,50, disposti trasversalmente rispetto all'asse della chiesa. Le caratteristiche di tali elementi autorizzano a ritenere che le strutture verticali da essi sostenute fossero dello stesso tipo di quelle presenti nella soprastante cattedrale romanica. D'altra parte, tenuto conto che la chiesa eretta da Bisanzio allo scopo di sostituire l'edificio preesistente con un altro di più ampie dimensioni richiama in modo evidente le caratteristiche dell'antica basilica, ripetendone in gran parte lo schema planimetrico, non c'è motivo per escludere che ad una cosi spiccata analogia dell'iconografia dei due edifici potessero corrispondere anche analoghe soluzioni strutturali. Risulterebbe in tal modo definitivamente chiarita la dibattuta questione della presenza delle colonne binate nella cattedrale romanica, da alcuni studiosi attribuita ad influenze esterne alla penisola italiana, richiamando esempi di architetture medievali della Francia settentrionale, collegate all'arrivo in Puglia dei Normanni in concomitanza con l'inizio di quel particolare fervore costruttivo che portò all'edificazione delle grandi cattedrali romaniche. Al contrario, una volta riconosciuto che le colonne abbinate corrispondono semplicemente al recupero ed alla riconferma di un modello strutturale già presente in loco ed appartenente ad un edificio presumibilmente costruito intomo al V secolo, come è attestato dai resti del mosaico pavimentale, risulta del tutto comprensibile e giustificata l'adozione di un lessico architettonico largamente diffuso nell'edilizia religiosa tra il V ed il VII secolo, con numerosi esempi, particolarmente nel vicino nordafrica, e nella stessa penisola italiana a Roma (Santa Costanza) e a Nocera Superiore (Battistero). Vengono così a trovare conferma alcune considerazioni esposte dal Krónig (W. Krònig, Contributi all'architettura pugliese del Medioevo, in "Atti del IX Congresso naz. di Storia dell'Architettura", Roma 1959) che, pur richiamando l'analogia con monumenti francesi, aveva posto in rilievo per primo la particolare affinità dello schema delle colonne binate di Trani con l'architettura paleocristiana. Oltre ai resti della basilica sono venuti alla luce altri elementi di notevole interesse relativi alle preesistenze nella medesima area ed alle vicende costruttive delle fabbriche ivi edificate. I resti del mosaico pavimentale ritrovati in sito corrispondevano alla sola zona dell'intera area dell'antica chiesa rimasta indenne da una serie di manomissioni operate nel corso dei secoli. La parte orientale, infatti, compresa tra il mosaico ritrovato e l'abside, venne scavata per realizzare l'ipogeo di San Leucio, le cui volte superano il livello del pavimento della chiesa, con la conseguente distruzione della corrispondente zona di mosaico. Nella rimanente parte dell'area della basilica, invece, il pavimento venne progressivamente distrutto per realizzare un gran numero di sepolture, in parte sistemate mediante lo scavo del banco tufaceo sottostante, altre poste a quote intermedie tra questo ed il pavimento. Le tombe risultano sempre orientale in direziono E-0, secondo l'asse principale della chiesa e sono, quindi, da attribuire ad un arco di tempo compreso tra l'edificazione della basilica paleocristiana e il XIX secolo come testimoniano le numerose monete ritrovate tra le sepolture più recenti. Dal livello a cui sono poste e dalle caratteristiche di esecuzione, oltre che dai numerosi reperti, è possibile classificarle in due gruppi; il primo appartenente alla necropoli realizzata nella basilica paleocristiana, il secondo risalente ad epoca successiva all'edificazione della cattedrale romanica, quando cioè nella cripta di Santa Maria, che corrispondeva parzialmente alla precedente basilica, venne mantenuta l'usanza di inumare i defunti. Le sepolture del primo gruppo si trovano disposte in parte ai livelli inferiori e sono scavate nel banco di tufo con sagoma antropomorfa per una maggiore larghezza nella parte mediana. In alcuni casi le tombe sono sovrapposte fino ad impegnare l'altezza contenuta tra il banco naturale ed il livello del pavimento. Le tombe di questo gruppo, sistemate superiormente al banco di tufo, sono realizzate mediante lastre di pietra in funzione di pareti laterali, mentre per la chiusura dei lati corti sono stati impiegati blocchi di tufo. In tre tombe, insieme con gli scheletri sono state rinvenute altrettante croci di fattura longobarda, due in argento ed una in lamina d'oro. Alcune lastre di pietra usate per comporre le tombe hanno rivelato la presenza di numerosi graffiti rappresentanti simboli cristiani, scritte e nomi di origine longobarda. Le tombe del secondo gruppo, realizzate dopo la costruzione della cattedrale romanica, sono, invece, eseguite secondo conformazioni varie in relazione allo spazio risultante dalla presenza delle sepolture più antiche. In generale sono realizzate con tecnica sommaria, delimitate da muratura in blocchetti di tufo e coperte con volte in muratura. Tra il copioso materiale frammentario rinvenuto nel terreno sconvolto per l'esecuzione delle sepolture sono stati ritrovati numerosi elementi provenienti dalla demolizione della basilica paleocristiana e dalla suppellettile esistente prima della costruzione della cattedrale romanica. Di particolare interesse sono risultati i frammenti di pavimentazione musiva e ad opus sedile, del rivestimento di intonaco dipinto, una lastra marmorea appartenente ad un altare con un'apertura centinaia, probabilmente la fenestella confessionis, un sarcofago risalente al V-VI secolo, due sculture in marmo pario raffiguranti teste di aquila e monete di varie epoche tra il IV e il XIX secolo. Gli scavi hanno, inoltre, rivelato l'esistenza di una costruzione anteriore alla basilica paleocristiana posta a circa m. 0,90 più in basso del mosaico già ritrovato. Gli scarsi elementi superstiti non consentono di definire ne la forma ne l'estensione di tale edificio, ma il rinvenimento di alcuni frammenti della decorazione pittorica dei muri che la delimitavano permettono di formulare l'ipotesi che possa trattarsi di una costruzione adibita al culto cristiano non molto più antica della basilica paleocristiana, demolita per far posto a questa. Ciò risulta, in particolare, dalla posizione e dalle caratteristiche di alcuni reperti ritrovati in condizioni di assoluta attendibilità. Infatti, come già detto, la sola zona non alterata dagli sconvolgimenti causati per la realizzazione delle sepolture era quella corrispondente al mosaico trovato in sito. Dagli scavi esguiti nelle zone immediatamente adiacenti è stato possibile osservare la particolare stratificazione del materiale sottostante al mosaico, che appariva chiaramente leggibile e rivelava, al di sotto degli strati di preparazione, un deposito di detriti ricco di frammenti di intonaco affrescato. Dopo la rimozione del mosaico, necessaria per consolidare il prezioso reperto che appariva del tutto inconsistente per l'elevato stato di aggregazione delle tessere, è stato possibile recuperare alcuni frammenti di dimensioni sufficienti per apprezarne le caratteristiche. E' risultato trattarsi di immagini probabilmente di soggetto biblico di età tardo-romana, attribuibili al IV-V secolo. Gli esigui elementi superstiti della costruzione più antica, consistenti in alcuni tratti di murature ed in una limitata zona pavimentata con lastre in pietra di forma irregolare, non consentono di aggiungere altro all'ipotesi dell'esistenza di un edificio di culto, che costituisce il momento iniziale di una continuità della presenza religiosa nel luogo dove oggi si erge la monumentale cattedrale.