The disintegration of the Roman Empire was followed by invasion of barbarian peoples: Eastern Goths, Gepidaes, Sarmatians, Avars, Slavs and others. Because of its advanced position at the border - limes, Belgrade suffered frequent attacks and destructions. The attacks coming from the north, across Pannonia, the Danube and Sava, were so hard that even Singidunum, an important military stronghold, could not resist them. The Huns captured it and completely destroyed it in 441. Singidunum lost its Roman inhabitants then. After the fall of the Huns, the town became a part of the Byzantine Empire once again in 454, but it was soon conquered by the Sarmatians, and later the Eastern Goths. However, already in 488, it became a Byzantine town again.
In the beginning of the VI century (in 512), the Byzantine emperor Anastasius settled the German tribes of Heruli in the immediate vicinity of the town, to defend it from the militant Gepidaes. The traces of material culture of the Germans have been found in the ruins of the former Roman town, on the west side of Lower Town. During the rule of the Byzantine emperor Justinian I, in 535, the town was rebuilt again and surrounded with strong walls. Thus Singidunum became a splendid and praiseworthy town. Most probably, Singidunum was then connected with Taurunum for the first time.
At the end of the VI century, while the Byzantines were occupied with wars in Africa and Asia, the Mongol tribes of Avars appeared in front of the walls of Singidunum, and after them came the first groups of the Slavs. After two sieges the Avars and Slavs conquer the town. There are numerous Byzantine historical sources about that siege and final fall of Singidunum. The name Singidunum disappeared after this barbarian invasion and the destruction of the town and it has never appeared again in the whole history afterwards. The traces of the Slavic material culture of that period have been found in Lower Town, Upper Town, Zemun, Ritopek and Višnjica. It was a more permanent beginning of the Slavicization of this town.
Around 630 the Serbian settlers come to this area. After this, there are no records about this town for more than two and the half centuries. The Avars and Slavs did not care about this town, because it had lost its status of a border stronghold. It was then within a wider region of the Balkan Peninsula which has been already conquered by the Slavs. In spite of that, archaeological discoveries indicate continuous life in the town and its surroundings. The town was mentioned again not until the IX century, under the Slavic name BEOGRAD (White Town - probably because of the walls made of white limestone). It was in a letter of April 16, 878 which Pope John VIII wrote to the Bulgarian prince Boris-Mihailo, about the dismissal of a Christian bishop Sergije. Later, this name appeared in several variants: ALBA GRAECA, GRIECHISCH WEISSENBURG, NANDOR ALBA, NANDOR FEJERVAR, CASTELBIANCO, ALBA BULGARICA.
Several centuries after the first mentioning of Belgrade as a Slavic town, various armies and conquerors control it by turns. The Franks were the first to reach Belgrade and destroy the Avars under the command of Charles the Great. On the ruins of Taurunum they founded a Frank settlement Malevila, which was after Slavicization changed to Zemln (Zemun). The rule of the Franks was replaced by Bulgarians, and they gave place to Hungarians. By the end of the X century, in the time of the great Samuel's state, Belgrade has already changed masters for a countless number of times. Already in 1018, it once again became a border stronghold of the Byzantine Empire. During the XI and XII centuries, the rival forces of Hungary, Byzantine Empire and Bulgaria fought for it.
During that period, the town was a transit point of numerous Crusades to the East, which left their destructive mark on it. After the Crusades of 1096 and 1147, 190,000 people pass through Belgrade in 1189, led by Frederick Barbarossa. This leader of crusaders saw Belgrade in ruins. Just how much the town suffered, we can judge by comparison with the record of the Arabian geographer and cartographer Idrisi, who in his "Itinerary of the Byzantine Road" of 1154 mentioned Belgraduk as a well-inhabited and lively town with many churches.