While there are no historical records that deal directly with the obscure and peripheral origins of Venice, tradition and the available evidence have led several historians to agree that the original population of Venice consisted of refugees from Roman cities near Venice such as Padua, Aquileia, Treviso, Altino and Concordia (modern Portogruaro) and from the undefended countryside, who were fleeing successive waves of Germanic invasions and Huns. Some late Roman sources reveal the existence of fishermen on the islands in the original marshy lagoons. They were referred to as incolae lacunae ("lagoon dwellers"). The traditional founding is identified with the dedication of the first church, that of San Jacopo at the islet of Rialto (Rivoalto, "High Shore"), given a conventional date of 421.

The last and most enduring irruption in the north of the Italian peninsula, was that of the Lombards in 568, leaving the Eastern Roman Empire a small strip of coast in the current Veneto, and the main administrative and religious entities were therefore transferred to this remaining dominion, centered upon the Exarchate of Ravenna, the local representative of the Emperor in the East. The Venetian tradition of the islanders' aid to Belisarius was reported in early histories to explain the largely theoretical link to Ravenna, and to the Eastern Emperor. New ports were built, including those at Malamocco and Torcello in the Venetian lagoon. The tribuni maiores, the earliest central standing governing committee of the islands in the Lagoon, dated from c. 568.

The Venetians traditionally having offered asylum to the Exarch, in flight from the Lombard Liutprand, the Byzantine domination of central and northern Italy was subsequently largely eliminated by the conquest of the Exarchate of Ravenna in 751 by Aistulf. During this period, the seat of the local Byzantine governor (the "duke/dux", later "doge") was situated in Malamocco. Settlement on the islands in the lagoon probably increased in correspondence with the Lombardo conquest of the Byzantine territories.

Sometime in the first decades of the eighth century, the people of the lagoon elected their first leader Ursus, who was confirmed by Byzantium and given the titles of hypatus and dux. He was the first historical Doge of Venice.

In 775-76, the bishopric seat of Olivolo (Helipolis) was created. During the reign of duke Agnello Particiaco (811-827) the ducal seat was moved from Malamocco to the highly protected Rialto, the current location of Venice. The monastery of St. Zachary and the first ducal palace and basilica of St. Mark, as well as a walled defense (civitatis murus) between Olivolo and Rialto were subsequently built here. Winged lions which may be seen in Venice are a symbol for St. Mark.

In 810, an agreement between Charlemagne and Nicephorus recognized Venice as Byzantine territory and recognized the city's trading rights along the Adriatic coast, where Charlemagne had previously ordered the pope to expel the Venetians from the Pentapolis. In 828, the new city's prestige was raised by the acquisition of the claimed relics of St. Mark the Evangelist from Alexandria, which were placed in the new basilica. The patriarchal seat was also moved to Rialto. As the community continued to develop and as Byzantine power waned, it led to the growth of autonomy and eventual independence.