La prima cittadella fortificata dal catapano bizantino Basilio Boioannes nel 1018, dopo il lungo abbandono dovuto alla deduzione di coloni e alla nascita di Venosa in epoca romana, comprendeva poche modeste abitazioni concentrate nell’attuale rione di San Lorenzo.
Le mura bizantine, non particolarmente elevate, servivano dunque a cingere e rafforzare la difesa di un abitato già naturalmente protetto dai ripidi pendii sui quali sorgeva, fin da epoca lontanissima. La roccaforte bizantina di Melfi era a sua volta al centro di un sistema difensivo che sorvegliava tutti i valichi dell’Appennino, per proteggere la provincia pugliese dai Longobardi. Questo vero e proprio vallo aveva diverse altre roccaforti, tra le quali Troia e Bovino, tutte tra loro collegate mediante piccole torri di guardia e segnalazione intermedie.
Raccontando l’arrivo dei Normanni nel 1041, il cronista medievale Amato da Montecassino descrive in effetti una città con mura non alte, ma comunque possenti per la loro collocazione molto elevata. Parte di questo tracciato è tuttora esistente, nel tratto che dal castello scende verso sud in senso antiorario fino a incontrare la prima porta.
Essa è chiamata Calcinaia poiché lungo la strada esterna, che tortuosamente si arrampica per raggiungere le mura partendo dalle rive della Melfia e dalle sorgenti dei Balnea poste a valle, sorge un sobborgo dove erano collocate le botteghe dei fornaciari e dei calcinai, destinate alla cottura dei laterizi e della calce da costruzione.
La porta Calcinaia conserva ancora i due bastioni laterali. All’interno del varco si apre uno slargo dove era il palazzo della Dogana, tuttora esistente, con un grande portale in ferro sul quale sono borchiati due leoni. Le torrette di questo tratto di mura sono di media dimensione, a forma di parallelepipedo con piccole feritoie e dotate di spalto. Esse costituiscono dunque sistemi di difesa antecedenti all’introduzione dell’artiglieria.
A conferma della caratterizzazione bizantina di questo primo nucleo urbano, uno dei vicoli di collegamento tra la sommità del colle e il percorso di ronda intramurario verso porta Calcinaia si chiama vico Grecia.