La Cattedrale e il Campanile sono intitolati alla Vergine fin dalla fondazione, come si legge dalla lapide di dedicazione incastonata sul lato nord del campanile, apposta dal vescovo Ruggero al termine della costruzione:

Hoc opus regium Regine Coeli comendet,

quod ex praecepto et salario

invictissimi regis Rogerii

et filii eius gloriosissimi regis, W.

Presul Rogerius

cum fideli populo melphiensi,

felici exito consumavit.

Anno Domini MCLIII

Questa opera dei re rammenti alla Regina del Cielo

che è stata felicemente completata per ordine e con il denaro

dell’invitto re Ruggero

e di suo figlio, il gloriosissimo re Guglielmo

dal vescovo Ruggero

con il fedele popolo di Melfi

nell’anno del Signore 1153.

Dalla dedica si comprende che in realtà l’opera, anche se commissionata da re Ruggero II, fu in realtà seguita sotto la direzione del vescovo di Melfi Ruggero e fu completata sotto la reggenza di Guglielmo il Malo, figlio di re Ruggero, il quale viene già definito re all’epoca della costruzione, anche se suo padre morirà soltanto nel successivo anno 1154.

Nella costruzione del campanile furono utilizzate largamente pietre di spoglio romane, provenienti dalla via Appia e dalla vicina Venosa. Lungo il perimetro della torre si possono individuare vari conci scolpiti a bassorilievo con figure geometriche, raffigurazioni, inserti di sculture e si leggono anche alcune iscrizioni risalenti a lapidi funerarie latine.

Lungo la cornice del primo marcapiano sono state incastonate tre protomi di leone, due sul lato nord e una sul lato ovest. Di queste, una reprime una testa d’ariete e l’altra un uomo. Una lapide funeraria romana riutilizzata ritrae invece una coppia di coniugi, che la tradizione popolare vuole sia l’effigie di re Ruggero e di sua moglie.

A sinistra è visibile l’insegna della bottega di un maniscalco, riconoscibile dalle tenaglie e ferri di cavallo, probabilmente riconducibile alla sua lapide sepolcrale.

In alto, ai lati delle bifore, si intravedono decorazioni geometriche a rombi policromi, con uso alternato di pietra calcarea e pietra vulcanica, anche se questo lato esposto a nord è maggiormente soggetto a opacizzarsi per effetto delle intemperie e quindi le decorazioni sono meno evidenti.