The precise details of Verona's early history remain a mystery. The origin of the name Verona is also unknown. One theory is it was a city of the Euganei, who were obliged to give it up to the Cenomani (550 BC). With the conquest of the Vaecame Roman (about 300 BC) Verona became a Roman colonia in 89 BC, and then a municipium in 49 BC; Verona had the franchise in 59.
The city became important because it was at the intersection of several roads. Stilicho defeated Alaric and his Visigoths here in 403. But, after Verona was conquered in (489 AD) the Gothic domination of Italy began; Theodoric built his palace there, and according to Irish legends that's what Verona was named after. It remained under the power of the Goths throughout the Gothic War (535–552), except for a single day in 541, when the Armenian officer Artabazes made an entrance. The defections that took place among the Byzantine generals with regard to the booty made it possible for the Goths to regain possession of the city. In 552 Valerian vainly endeavoured to enter it, but only when they were fully overthrown, the Goths surrendered it.
In 569, it was taken by Alboin, King of the Lombards, in whose kingdom it was, in a sense, the second most important city. There, Alboin himself was killed by his own wife in 572. The dukes of Treviso often resided there. At Verona Adalgisus, son of Desiderius, in 774 made his last desperate resistance to Charlemagne, who had destroyed the Lombard kingdom. Verona was then the ordinary residence of the kings of Italy, the government of the city becoming hereditary in the family of Count Milo, progenitor of the counts of San Bonifacio. From 880 to 951 the two Berengarii resided there. Otto I ceded to Verona the marquisate dependent on the Duchy of Bavaria.
The reign of his son Alberto as capitano (1277–1302) was one incessant war against the counts of San Bonifacio, who were aided by the House of Este. Of his sons, Bartolomeo, Alboino and