Dopo l’anno 1000 nella Chiesa cominciavano a diffondersi nuove idee provenienti da nord. Anche in Puglia, grazie alle spade normanne alleate con i papi del tempo, la liturgia latina occidentale si imponeva con la forza sull’antico rito greco e l’autorità del papa si affermava al di sopra degli altri vescovi e del potere laico del kaiser, costretto a recarsi penitente a Canossa. La riforma nasceva nei monasteri benedettini, da cui provenivano gli alti prelati presenti a Melfi in occasione di vari concili: il fine diplomatico Ildebrando di Soana (futuro Gregorio VII), il priore Arnaldo di Acerenza e l’abate Oddone di Lagery (Urbano II), tutti formati nell’abbazia francese di Cluny. O il principe longobardo Desiderio da Benevento (Vittore III), abate di Montecassino.

Anche le scelte architettoniche furono influenzate dall’autorevolezza di questi religiosi quando, elevato a duca di Puglia nel concilio di Melfi del 1059, il capo normanno Roberto il Guiscardo iniziò un importante ampliamento urbanistico della sua capitale, la cui cinta muraria correva allora lungo la Ruga Grande, attuale via Vittorio Emanuele II. Appena fuori dalla portierla di Santa Lucia, allo sbocco della via Novella si apriva un ampio pianoro, ideale per la costruzione di un grande complesso ecclesiastico da destinare a sede cattedrale del vescovo, al posto dell’ormai angusta chiesa di San Pietro dentro le mura. Roberto finanziò largamente la nuova diocesi con ripetute donazioni e nel 1076 le assegnò la decima dei proventi annui della bagliva, la tassa per il controllo dei pesi e misure dei prodotti.

Di questa prima costruzione purtroppo non resta quasi nulla, a causa dei frequenti e disastrosi terremoti verificatisi nel corso dei secoli. Tuttavia si possono fare alcune ipotesi sull’antico impianto osservando l’abbazia benedettina di Sant’Ippolito a Monticchio, l’abbazia incompiuta della SS. Trinità di Venosa e la Cattedrale di Acerenza, oppure studiando alcuni documenti e quadri antichi. Similmente a questi edifici coevi, anche la cattedrale di Melfi aveva una pianta a tre navate incrociata da un transetto e chiusa da un catino absidale curvo, ben visibile alle spalle di un austero altare basilicale. La facciata, romanica, era abbellita da un grande rosone.

Nel 1130 Ruggero II, conte di Sicilia e nipote di Roberto il Guiscardo, riunificò nelle sue mani tutti i domini normanni del Sud Italia fino all’Abruzzo. Ne nacque un conflitto con papa Innocenzo II e San Bernardo da Chiaravalle, sostenuti dai cavalieri Templari, mentre Ruggero si schierò con l’antipapa Anacleto II della potente famiglia ebraica dei Pierleoni. In cambio di questo appoggio, Ruggero ricevette da Anacleto il titolo di Re di Sicilia durante il concilio di Melfi del 1130 e per celebrare l’evento iniziò un ampliamento del complesso della Cattedrale, che sarà portato a termine da suo figlio Guglielmo il Malo.