Durante le invasioni barbariche la città subì assedi e occupazioni dapprima dagli Eruli guidati dal generale romano Odoacre, poi dagli Ostrogoti, dai Saraceni e infine dai Longobardi che vi insediarono una sede di gastaldato, secondo la ripartizione amministrativa del loro ducato.

Con l’arrivo dei Normanni e la nascita del Regno di Sicilia Venosa perse progressivamente importanza in favore della vicina Melfi, anche se la presenza del sacrario di famiglia degli Altavilla consentiva un riguardo particolare.

Nella ripartizione delle funzioni amministrative l’imperatore Federico II fece ampliare un fortilizio longobardo per ubicarvi il Tesoro del Regno, ossia l’amministrazione delle finanze, nel palazzo oggi sede conventuale dei Padri Trinitari. A Venosa nacque probabilmente Manfredi, figlio naturale di Federico II e di Bianca Lancia, suo successore nella corona di Sicilia.

La testimonianza più importante della Venosa medievale è certamente l’Abbazia della SS. Trinità. Caduta in abbandono in età alto medievale, l’area dell’odierno parco archeologico divenne una necropoli. Nelle sue immediate adiacenze, sui resti dell’antico tempio di Imene, furono costruite due chiese che compongono la cosiddetta Insula Episcopalis, di cui la prima è visibile sotto il pavimento dell’attuale chiesa antica.

La seconda chiesa è situata lungo il suo lato occidentale, è suddivisa in tre navate e termina con un’abside trilobata coronata da un deambulatorio esterno. Al centro è collocato un fonte battesimale esagonale e, nelle vicinanze, un battistero cruciforme. Su questo complesso i Normanni iniziarono i lavori di ampliamento per una grande abbazia che facesse da sacrario per le loro tombe, usando materiali di spoglio dei vicini resti romani, ma l’opera restò incompiuta conferendo particolare fascino a tutto l’insieme.

Nel complesso la chiesa antica richiama lo stile di una basilica romana, ancora fedele in epoca paleocristiana, dominato dalla navata centrale che si chiude con il catino absidale. La navata è suddivisa in quattro sezioni trasversali da grandi archi. La facciata d’ingresso romanica, anche se l’attuale è il frutto della sovrapposizione nei secoli di ben quattro facciate diverse.

All’interno si trovavano un tempo le tombe dei quattro fratelli Altavilla: Wilhelm, Drogon, Umfred e Rudbert detto il Guiscardo, primo duca di Puglia e conquistatore di Bari, Salerno e Palermo, insieme con la tomba della prima moglie di quest’ultimo, Alberada di Buonalbergo. Nel ’400 durante una ristrutturazione le tombe degli Altavilla vennero eliminate e riunite in un unico sepolcro intitolato a Roberto il Guiscardo, mentre la tomba di Alberada è ancora intatta.

L’arca sepolcrale degli Altavilla si trova sulla destra, mentre a sinistra è visibile la tomba di Alberada, ripudiata dal marito che le preferì la principessa longobarda Sichelgaita di Salerno. Figlio di Alberada fu Boemondo d’Altavilla, eroe della I crociata e principe di Antiochia, sepolto a Canosa come recita l’iscrizione posta sull’architrave del sepolcro:

« GVISCARDI CONIVX ABERADA HAC CONDITVR ARCA

SI GENITVM QVÆRES HVNC CANVSINVS HABET »

« Aberada, moglie del Guiscardo, è sepolta dentro quest’arca.

Se cercherai il figlio, Canosa lo possiede »

Accanto alla tomba di Alberada si trovano i sepolcri di due degli Acciaioli: Raffaele ed Emilio, signori fiorentini di Melfi in epoca angioina. Sotto il pavimento sono visibili i resti della basilica paleocristiana e una porzione di mosaico di una domus di età imperiale. Nella chiesa si trova anche la cosiddetta colonna dell’amicizia, che secondo la tradizione concede eterna armonia alle persone che vi girino intorno tenendosi per mano e fecondità alle giovani spose che vi si comprimano.

Alle spalle dell’abside sorge l’Incompiuta, naturale prolungamento e ampliamento della chiesa antica, mai ultimata a causa della soppressione del monastero benedettino da parte di papa Bonifacio VIII, che nel 1297 lo assegnò ai Cavalieri Ospedalieri di San Giovanni in Gerusalemme, poi Ordine di Malta. L’Ordine però preferì dimorare all’interno della città, nel palazzo cosiddetto del Balì.

All’ingresso si trova un’iscrizione propiziatoria che invoca la protezione divina sul tempio, sulla quale si vede un agnello con la croce, simbolo dell’Ordine di Malta. Molti dei materiali utilizzati sono di spoglio: tra questi l’epigrafe proveniente dal vicino anfiteatro con l’elenco dei gladiatori della scuola di Salvio Capitone e diversi bassorilievi funerari come la stele della famiglia del console Lucio Cornelio Cinna. Interessante è anche un bassorilievo che ritrae tre vipere, simbolo longobardo.

Testimonianze medievali in città sono soprattutto le fontane. Tra queste la fontana angioina del 1298, identificata due leoni in pietra che ghermiscono un ariete e una colonna centrale, provenienti da resti romani, o la fontana di Messer Oto, del 1313, anch’essa sormontata da un grande leone in pietra. Di epoca rinascimentale è invece la fontana di San Marco con annesso lavatoio pubblico, situata alle spalle della Cattedrale.