After the region fell to the Romans in 168 BC, it became part of the province of Macedonia. The central portion of modern Albania was later split off as Epirus nova ("New Epirus"), while the southern remained under Epirus vetus and the northern parts belonged to Praevalitana.
In the first decades under Byzantine rule (until 461), Epirus nova suffered the devastation of raids by Visigoths, Huns, and Ostrogoths. In the 4th century barbarian tribes began to prey upon the Roman Empire. The Germanic Goths and Asiatic Huns were the first to arrive, invading in mid-century; the Avars attacked in 570; and the Slavic Serbs and Croats overran the region in the early 7th century. About fifty years later, the Bulgars conquered much of the Balkan Peninsula and extended their domain to the lowlands of what is now central Albania. In general, the invaders destroyed or weakened Roman and Byzantine cultural centers in the lands that would become Albania.
Since the 1st and 2nd century, Christianity had become the established religion in most of the eastern Roman Empire, supplanting pagan polytheism. But, though the country was in the fold of Byzantium, Christians in the region remained under the jurisdiction of the Pope of Rome until 732. In that year the iconoclast Byzantine emperor Leo III the Isaurian, angered by archbishops of the region because they had supported Rome in the Iconoclastic Controversy, detached the church of the province from the Roman pope and placed it under the patriarch of Constantinople. When the Christian church split in 1054 between the East and Rome, the region of southern Albania retained its ties to Constantinople while the north reverted to the jurisdiction of Rome. This split marked the first significant religious fragmentation of the country.
Later, in the early 9th century, the Byzantine government established the theme of Dyrrhachium, based in the city of the same name and covering most of the coast, while the interior was left under Slavic and later Bulgarian control. Full Byzantine control over modern Albania was established only after the Byzantine conquest of Bulgaria in the early 11th century.
In his History written in 1079-1080, Byzantine historian Michael Attaliates referred to the Albanoi as having taken part in a revolt against Constantinople in 1043 and to the Arbanitai as subjects of the duke of Dyrrachium. It is disputed, however, whether that refers to Albanians in an ethnic sense. However a later reference to Albanians from the same Attaliates, regarding the participation of Albanians in a rebellion in 1078, is undisputed. At this point, they are already fully Christianized. In the late 11th and 12th centuries, the region played a crucial part in the Byzantine–Norman Wars; Dyrrhachium was the westernmost terminus of the Via Egnatia, the main overland route to Constantinople, and was one of the main targets of the Normans (cf. Battle of Dyrrhachium (1081)). Towards the end of the 12th century, as Byzantine central authority weakened and rebellions and regionalist secessionism became more common, the region of Arbanon became an autonomous principality ruled by its own hereditary princes.
After the Fourth Crusade, the region came under the control of the Despotate of Epirus, but its control was never firm. Serbian influence began to be strongly felt at this time, as well as those of Venice and later of the Kingdom of Sicily, as both powers tried to gain control of coastal Albania for their purposes.
The new administrative system of the themes, or military provinces created by the Byzantine Empire, contributed to the eventual rise of feudalism in Albania, as peasant soldiers who served military lords became serfs on their landed estates. Among the leading families of the Albanian feudal nobility were the Thopias, Balshas, Shpatas, Muzakas, Aranitis, Dukagjins, and Kastriotis. The first three of these rose to become rulers of principalities that were practically independent of Byzantium.
In 1258, the Sicilians took possession of the island of Corfu and the Albanian coast, from Dyrrhachium to Valona and Buthrotum and as far inland as Berat. This foothold, reformed in 1272 as the "Kingdom of Albania", was intended by the dynamic Sicilian ruler, Charles of Anjou, to become the launchpad for an overland invasion of the Byzantine Empire. The Byzantines however managed to recover most of Albania by 1274, leaving only Valona and Dyrrhachium in Charles' hands. Finally, when Charles launched his much-delayed advance, it was stopped at the Siege of Berat in 1280–1281. Albania would remain largely part of Byzantine empire until the Byzantine civil war of 1341–1347, when it fell shortly to the hands of the Serbian ruler Stephen Dushan.