Before the present-day Vienna came into being, the site was occupied by Vindobona, a Celtic settlement, later taken over by the Romans and turned into a military camp. That's when the history of Vienna really begins. The camp was founded in this area in the 1st Century AD, by Emperor Legio X Gemina in the Inner City of what today is Vienna. In the year 212, the settlement was granted the status of a municipum, after colonia the second-highest class of a Roman city. The avenues of the present-day First District of Vienna show where the camp walls and moats were located.

During the chaos of the Migration Period in Europe, between 300 AD and 700 AD, the Romans left Vindobona. It was the time of a gradual transition form Antiquity to Middle Ages. The migration involved such peoples as the Franks, Vandals, Goths, and other Germanic and Slavic tribes. Historians propose various explanations of the mass migration, which include climatic changes, the invasions of the Huns, and overpopulation.

In the early 5th Century, in Vienna, houses started to replace the Roman walls. Only parts of the fortifications remained after the 5th Century and they were adapted to different uses by the inhabitants of the city. The first mention of Vienna, however, dates back to 881 AD, when a battle against the Magyars (ethnic Hungarians) was fought. In 500 AD, graves from that period were discovered near the early centre of Vienna, called Berghof, in the area around the side street Salvatorgasse. Byzantine coins from these times have also been unearthed in present-day First District, providing a proof of considerable commerce that took place in those years. In the 6th Century, the area was controlled by the Germanic tribe of Lombards, and Avars who were followed later by the Slavs. 'The Salzburg Annals' chronicle mentions the 955 AD battle of Lechfeld, against the Magyars, that ended with Emperor Otto I's victory over the Hungarians, right at the onset of the Middle Ages.