Dopo l’epoca bizantina, un primo significativo ampliamento del nucleo urbano di Melfi fu compiuto dai fratelli normanni Guglielmo Braccio di Ferro, Drogone e Umfredo Altavilla, i quali cominciarono l’edificazione di una motta difensiva sulla sommità del colle, secondo la tecnica nordica che prevedeva lo scavo di un fossato e il riporto del materiale di risulta in sopraelevazione al centro, in modo da creare un dosso sul quale costruire un fortilizio di legno.

Con l’elezione di Melfi a capitale dei territori che andavano conquistando, anche l’abitato fu ampliato per ospitare dodici importanti residenze, con altrettante piazze per i dodici cavalieri normanni, ai quali venivano assegnati i vari pezzi di territorio pugliese e città che cadevano rapidamente sotto il dominio di questi avventurieri nordici.

Un quarto fratello Altavilla, Roberto il Guiscardo, dopo essere stato nominato duca di Puglia da papa Niccolò II nel Concilio di Melfi del 1059, ampliò ulteriormente l’abitato realizzando un palazzo ducale in pietra al posto della originaria motta in legno.

In quegli stessi anni Melfi fu elevata a diocesi con la nomina del primo vescovo Baldovino. Fu perciò istituita la prima sede cattedrale della città, nella chiesa di San Pietro. Questa si trovava sul versante opposto del colle, verso nord, nei pressi dell’antica via bizantina che conduceva alle altre roccaforti di Puglia e in particolare a Troia.

La cinta muraria si estese quindi verso nord-est, per abbracciare anche questo versante. In essa fu aperta un’ulteriore porta sulla via di Troia, chiamata appunto Troiana e di cui oggi resta solo il varco stradale. Il progressivo ampliamento urbano all’interno di questo nuovo perimetro si sviluppa con un sistema a imbuto e raggiera, mediante la creazione di varie strade longitudinali che dalla parte alta scendono a valle, per ricongiungersi tutte in prossimità della nuova porta principale che si apriva sulla prima piazza esterna di mercato, oggi piazza Umberto I.