In the 8th century, the Republic of Venice had pro-Frankish, pro-Byzantine, and pro-Lombard factions during the time of Byzantine decline. Charlemagne had designs on Venice, but failed to conquer it. As a result, Charlemagne recognized Venice as Byzantine territory. Over time, as the Byzantine declined, Venice obtained special privileges (such as exemption from trade tax) and became de-facto independent.

Therefore while the Kingdom of Italy based in Lombardy became part of the HRE, Venice was able to remain (de facto) independent.

In the aftermath of the the collapse of the Western Roman Empire and the formation of the Kingdom of Francia, a process took place in northern Italy which defined the course of this are throughout the middle ages. Charlemagne defeated the Lombards in 774 and kickstarted the involvement of Northern Italy in what would later become the HRE. This era also saw various alliances between Frankish kings and the Pope (and also the establishment of the Papal State).

Venice, however, was an exception. After the division of the Roman Empire and the collapse of the western part, Venice remained part of the Eastern Roman Empire (or the Byzantine Empire). At this time, Venice started gaining wealth. It was caught up in the struggle between Charlemagne and the Eastern Roman emperors over the question of who the rightful "Roman Emperor" was – as the idea at the time was that there could only be one emperor at a time. From the 9th century onwards, Venice gradually became independent, and although it was de jure still part of the Byzantine Empire, both empires gradually started recognizing Venice as an independent entity, allowing it to become an important city for trade between both empires and other territories. There were, however, struggles within the city (not dissimilar to the conflicts between Guelphs and Ghibbelines in other Italian cities a few centuries later), with different fractions supporting one emperor or the other.

From then onwards, Venice was simply too wealthy, big and important to annex or similar by the HRE. It was accepted as independent and became the powerful trade nation it is famous for. Throughout the centuries, Venice was caught up in many conflicts between the various powers of Europe, but via diplomacy and also military action, it managed to remain independent until the Napoleonic Wars, when its decline began. After being occupied by Austria, Venice finally became part of the newly founded Kingdom of Italy in 1866.

Pepin, king of Italy and son of Charlemagne besieged the city in 810 and was beaten back. The siege lasted six months and Pepin's army was ravaged by the diseases of the local swamps and was forced to withdraw. A direct assault on the Venetian lagoon has only been accomplished once, by Napoleon. A few months later Pepin died. Venice was also a sort of vassal state of Byzantium, they were functionally independent, and culturally they were much closer to Constantinople than to Milan. In the aftermath of the failed siege Charlemagne acknowledged that Venice was a Byzantine territory and that he had no claim on it.

Ok, let me also take a shot at this, as I think some points haven't been made totally clear yet.

Unlike /u/stefan2494 writes, Venice wasn't made part of the Eastern Roman Empire after the final partition in 395. The city didn't even exist back then. The lagoon at the head of the Adriatic were Venice would later originate first came under the control of Constantinople when the Ostrogothic kingdom in Italy was conquered by the armies of Justinian I in the 6th century. After the initial invasion of the Lombards in 568 the remaining parts of Byzantine Italy were restructered into a governmental unit called an exarchate with it's capital in Ravenna. When the Lombard king Aistulf finally managed to capture Ravenna in 751 Byzantine rule over Northern Italy largely collapsed. This however was not the case in the north adriatic lagoon because the Byzantine fleet, although already challenged by the Arabs, was still intact and able to support such far flung outposts. The region was still called by its ancient name Venetia, after the tribe of the Veneti that had settled there before the Roman conquest. It was governed by a military official called a dux. You may recognize the italian version of this title: doge. The seat of that official was moved between several places in the lagoon like Eraclea or Malamocco until he finally settled on the island were Venice is located today.

This became necessary for security reasons because in 810 the Carolingian Franks attacked. Charlemagne, the frankish king, had already conquered the Lombard kingdom in Italy and let himself be crowned Roman Emperor by the Pope in 800. As this title was already claimed by the emperors in Constantinople conflict broke out. To put pressure on the Byzantines the Franks attacked their holdings in the Adriatic. The doge was besieged in his lagoon by Charlemagne's son Pepin in 810. As Byzantium had maritime superiority and the land in the lagoon comprised mostly of swamps that siege had to be lifted eventually. In 812 an agreement was reached in which both sides acknowledged each other as emperors. The lagoon stayed under Byzantine control while the rest of Northern Italy was still part of Charlemagne's domain and by that of the later Holy Roman Empire.

By that time the construction of the city of Venice was well under way. The first doge's palace was erected in 811. In 828 merchants from the lagoon stole the relics of the Evangelist Mark from Alexandria in Egypt and took them home were a predecessor of today's St Mark's Basilica was build soon after. Gaining independence from Byzantium was a very gradual process. While Constantinople was tied up in its struggles with the Arabs in Anatolia and the Bulgars and Slavs in the Balkans Venice was left relatively undisturbed. Already in 697 had the people of the Lagoon obtained the right to elect their doge themselves. To insure themselves of the doge's continiued loyalty the Byzantine emperors showered him with ever more grandiose titles like spatharios (807), protospatharios (879) or Protosebastos (1082). Meanwhile Venice, growing richer and richer thanks to its trade connections, build up its own fleet and began to claim parts of the coast of Dalmatia on the eastern shore of the Adriatic. By the 11th century the doge of Venice was treated as an independend player by pretty much everyone else. The Holy Roman Emperor Otto III visited the city in 1001 to gain its support and to see the relics of St. Mark. The Byzantine Emperor Basil II (958-1025) granted venetian merchants wide ranging privileges, which were expanded by Alexios I (1081-1118). In return the venetian fleet supported byzantine campaigns in southern Italy. I'm going to end here with my recount of venetian history as by then even the Byzantines had clearly stopped treating Venice as part of their realm or even as a vassal state. Soon after the Holy Roman Empire's control over Northern Italy would loosen and Venice became one of several independent italian city states.

The ties that bound Venice to the east can still be seen today when you visit the city. St. Mark's Basilica combines late antique elements with ones from medieval Byzantium as well as the latin west. Byzantine artists worked in the city for centuries. Much of the medieval art from the lagoon is even called veneto-byzantine by art historians. On the other hand Venice always was very much part of latin Northern Italy. Its citizens spoke a form of Proto-Italian. Its church ultimately was subordinate to the Pope in Rome and not the Patriarch of Constantinople. St. Mark's Basilica was meant to rival the cathedrals of Aquileia or Pisa. Medieval Venice is really a fascinating case of cultural syncretism, much like Norman Sicily or Nemanjid Serbia.