Nel IV secolo i barbari erano oramai un tutt'uno nella vita civile e militare con l'Impero.
Nel 403 Alarico, re dei Visigoti, dalla Dalmazia venne in Pianura Padana e si asseragliò in Verona. Fu però sconfitto da Stilicone, barbaro ma romanizzato.
Nel 452 Attila, re degli Unni, con mezzo milione di uomini lasciò una scia di distruzione che terminò proprio a Verona. Fu fermato a Salionze sul Mincio da Papa Leone I e da una legazione imperiale. Fu convinto dalle parole del Santo e dalla promessa di un tributo annuo. Ritornò in Pannonia.

Odoacre, capo degli Eruli e dei Turcilingi, che facevano parte dell'esercito imperiale, depose Romolo Augustolo e mise fine all'Impero Romano d'Occidente nel 476.
Odoacre non ebbe investiture ma governò di fatto e lasciò un buon ricordo nei Veronesi. Non mutò nulla del governo precedente, e da ariano non avversò i cattolici. Applicò una regola romana del passato per pacificare il suo esercito, confiscò ai latifondisti un terzo delle terre e le distribuì ai suoi soldati, rilanciando l'agricoltura e l'economia. Diede all'Italia pace e sicurezza. Fermò i Rugi; ma non poté fermare gli Ostrogoti di Teodorico, mandati in Italia da Zenone, imperatore d'Oriente. Odoacre si fortificò a Verona nel 489 ma fu sconfitto e poi ucciso.

Sotto Teodorico (493-526), Verona fu praticamente capitale dei Goti: era il centro militare più importante e la sede preferita del re, che le restituì il suo splendore e rialzò le mura atterrate dalle precedenti incursioni barbariche. Seguì la strategia di Odoacre, ariano come lui, ma come ritorsione alla persecuzione da parte di Giustino verso gli Ariani a Bisanzio, vessò i Romani divenuti sospetti uccidendo il fedele consigliere Simmaco e fece arrestare Albino e Boezio, suo segretario che in prigione scrisse il famoso De Consolatione Philosophiae.
Con la morte di Teodorico i Bizantini, con un esercito di soli 10.000 uomini, occuparono con Narsete l'Italia fino a Brescia. Alboino, re dei Longobardi, interruppe il breve dominio greco su Verona. Nel 568 si fortificò in Verona dominando l'Italia settentrionale e lasciò ai Bizantini Ravenna ed il resto d'Italia. Questi fatti furono raccontati nella Historia Langobardorum sotto il regno di re Desiderio.

Per alcuni anni i Longobardi imposero con violenza il loro potere, uccidendo, distrussero chiese e vescovadi, rapinarono ed espropriarono il possibile. In una ventina d'anni però si convertirono al cristianesimo e cambiarono atteggiamento, al punto di proibire i matrimoni fra parenti anche lontani al fine di favorire la fusione fra i popoli (Liutprando nel 730 circa).
Autari, re longobardo, pur legatissimo a Verona, spostò la capitale a Pavia. Da questo punto i longobardi cattolici si slegarono dalla storia veronese e si legarono a quella italiana.
Come una specie di rifusione, fecero nascere con lasciti abazie e conventi.

Interno della Basilica di San Zeno

E fu nel 774, proprio a Verona, che Carlo Magno sconfisse l'ultimo re dei Longobardi: Adelchi, fatto che segnò la fine del periodo Longobardo. Manzoni ha trasposto questo fatto storico in nella sua tragedia omonima, spostando tuttavia l'accento sul dramma personale di Ermengarda, figlia di desiderio ripudiata e abbandonata da Carlomagno. Il figlio di Carlo Magno, Pipino che soggiornò a lungo nell'Abbazia di San Zeno e fu seppellito a Verona. Diede un nuovo grande impulso allo sviluppo della città con l'aiuto di Ireneo Pacifico, arcidiacono della Cattedrale ed in particolare, in mezzo ad altri monumenti costruì la Basilica di San Zeno sui resti di una primitiva chiesa paleocristiana sorta presso la tomba del santo .

Alla caduta dei Carolingi iniziò sulla città il dominio straniero e Verona entrò a far parte della Marca di Baviera e successivamente della Marca di Carinzia. Di questo periodo il vescovo Raterio, uno dei più illustri studiosi del medio evo italiano, che venne più volte rimosso e reinsediato per i cattivi rapporti con i governanti e il clero locale, di cui contestò severamente le malversazioni e l'eccessivo interesse ai beni materiali.
Intorno al 950 fu creata la Marca Veronese con l'inizio del potere della famiglia Sanbonifacio. Con l'unione delle corone di Germania e d'Italia (961) Verona fu l'unica città italiana dove i re tedeschi soggiornarono, sempre presso l'abbazia di San Zeno. Vi si svolsero numerose diete e furono stipulati numerosi accordi con altri governanti italiani.