Sul primo provvisorio edificio, probabilmente ancora di legno e terra, venne poi costruito il primo manufatto in pietra, con funzione di palazzo ducale, su iniziativa di Roberto il Guiscardo. Proprio a Melfi il capo banda normanno fu proclamato Duca di Puglia, Calabria e della Sicilia ancora da conquistare, in un concilio indetto da papa Niccolò II Nel 1059.
Il palazzo aveva pianta quadrata ed era munito di quattro torri negli angoli, tre delle quali tuttora ben visibili anche se ormai inglobate nel palazzo centrale, con una costruzione posticcia che ospita oggi la biglietteria del museo e la sovrastante saletta. Gli ingressi erano collocati sui due lati opposti est e ovest, in prossimità della cinta muraria, nella cui corrispondenza tuttora si trovano quelli di epoca angioina.
Nel palazzo ducale fu tenuto prigioniero il generale romano Exaugusto Boioannes, catturato dai Normanni durante la lotta per la conquista della Puglia, ma anche numerosi baroni che si ribellavano spesso all’autorità del duca, come Riccardo di Capua e Pietro di Trani.
Nel 1089 papa Urbano II vi tenne un concilio nel quale pose le basi per l’avvio della prima crociata, chiudendo un accordo politico con i capi normanni Ruggero di Sicilia e Boemondo d’Altavilla, rispettivamente fratello e figlio del defunto Roberto il Guiscardo.
Nel 1130 a Melfi si tenne un altro concilio nel quale l’antipapa Anacleto II confermò a Ruggero II il titolo di Re di Sicilia, dando vita al più grande e longevo stato esistente in Italia fino all’Unità del 1861.
Nel 1137 la città ospitò l’imperatore Lotario di Supplimburgo che partecipò all’ultimo dei sei concili di Melfi, indetto da papa Innocenzo II.