Map of Scandza based on Jordanes: Herulian homeland is located in Southern Sweden
The Herules are possibly first mentioned as the "Hirri" in the first century AD writings of Pliny the Elder. Plinius stated that the territory extending from the Vistula river, as far as Eningia (probably he meant Feningia = Finland), is inhabited by the following nations: the Wends, the Scirii and the Hirri. (The Scirii were another East Germanic people who, like the Herules, moved from somewhere near the Sea of Azov to the Danube, during the times of the Huns and Goths.)
The 6th-century AD chronicler Jordanes reported a tradition that they had been driven out of their homeland by the North Germanic Dani, which places their origins in the Danish isles or southernmost Sweden.
This origin above was a general mistake caused by a Danish historian in 1783 AD. There are no sources at all indicating a Scandinavian origin as the remark of Jordanes is now regarded to refer to a meeting between Herules and Danes contemporary with the one of Procopius. The news was spread by an envoy returning from Scandinavia in 548AD and both historians finished their works in Constantinople 551-553AD – making it extremely unlikely that the two meetings should be separated by 300 years. Furthermore, the etymology of the Heruli was associated with the Sea of Asov according to Jordanes. He could not in the same time regard their origin as Scandinavian. The Herules were possibly a mix of Goths, Sammartians and Bosporanians at the eastern bank of the Dnepr. The connection between the Western Heruli in Frisia (Harlingen?) and the Eastern is unknown, but a group may in the 3rd century have crossed Europe against east or west.
The first clear mention of the Herules by Roman writers is generally taken to be in the reign of Gallienus (260-268 AD). This is based on accepting the later writer Jordanes, who equated the Herules of his time and the "Elouri" mentioned by Dexippus. These Elouri accompanied the Goths and other "Scythians" ravaging the coasts of the Black Sea (today southern Ukraine) and later entering the Aegean, a "sea-borne invasion of unprecedented size took place in the spring of 268". Sacks of Byzantium, Chrysopolis, Lemnos, Scyros, Sparta, Corinth and Argos followed.
Armed groups moved around Greece and the Balkans, and the East Roman military took several years to contain the threat. After suffering a crushing defeat at the river Nestos one surrendering Herul chief named Naulobatus became the first barbarian known from written records to receive imperial insignia from the Romans. It seems to have been the Herules specifically who sacked Athens despite the construction of a new wall, during Valerian’s reign only a generation earlier. This was the occasion for a famous defense made by Dexippus, whose writings were a source for later historians. The Romans had a major victory at the Battle of Naissus in 269, apparently a distinct battle from that at the Nessos, where a Herul chieftain named Andonnoballus is said to have switched to the Roman side. But attacks continued until 276.
Herules were also seen in western Europe before the empire of Attila. In 268 Claudius Mamertinus reported the victory of Maximian over a group of Herules and Chaibones (known only from this one report) attacking Gaul. It is believed that it was from this time that the Romans instituted a Herul auxiliary unit, the Heruli seniores, who were stationed in northern Italy and often associated with the Batavian Batavi seniores.
In 406, a large number of barbarian groups crossed the Rhine, entering the Roman empire, and the Herules appear in the list of peoples given by the historian Jerome. However this list is sometimes thought to have drawn on historical lists for literary effect. A more difficult phenomenon for historians to explain is the appearance in these times of significant sea-borne raiding groups of Herules, as far away as northern Portugal, by this time under control of Suevi who had been involved in the 406 Rhine crossing approximately 50 years earlier. This was reported by Hydatius. Some historians have even speculated that there must have been a western Herul group with a power base somewhere in northern Europe, but not all historians agree that this assumption is justified. It has for example been suggested that these Herules were working under the Visigothic kingdom in nearby southwestern France, and descended largely from eastern peoples who had been in the Roman army of the goth Alaric I in Italy, and who were heavily involved in conflict with the Suevi and other kingdoms in Iberia at the time.
In their apparent place of origin, near the Sea of Azov, Jordanes reports that much earlier Ermaneric the Goth conquered the Herules, whose leader at this time was named Alaric (or Halaric), a name which would be used several times in later history of the East Germanic peoples including the Goths. After this nothing is heard of them again in that region.
After the death of Attila his sons and their Ostrogoth allies lost power over the various peoples of his empire at the Battle of Nedao in 454. The centre of this alliance was now settled upon the Roman border. Herules on the winning side of the Gepids were subsequently among the several peoples now able to form a kingdom on the northern banks of the Danubian area. The losing Ostrogothic forces moved into the Balkans, under Byzantine influence.
The Herul kingdom, apparently under a king named Rodulph, was established north of modern Vienna and Bratislava, near the Morava river, and possibly extending as far east as the Little Carpathians. They ruled over a mixed population including Suevi, Huns and Alans. From this region they pushed westwards, on one occasion attacking Passau, and eventually established control on the Roman (south) side of the Danube, north of Lake Balaton in modern Hungary. They do not appear in early lists of Odoacer's allies after Nedao, but they were apparently able to take over the kingdoms of the Suevi and Scirii, who had been under pressure from the Ostrogoths, who continued to press their old allies from the Balkans. Odoacer, the commander of the Imperial foederati troops who deposed the last Western Roman Emperor Romulus Augustus in 476 AD came to be seen as king over several of the Danubian peoples including the Herules, and the Herules were strongly associated with his Italian kingdom. The Herules on the Danube took control of the Rugian territories, who had become competitors to Odoacer and been defeated by him in 488. However Herules suffered badly in Italy, as loyalists of Odoacer when he was defeated by the Ostrogoth Theoderic. By 500 the Herule kingdom on the Danube had made peace with Theoderic and become his allies. Paul the Deacon also mentions Herules living in Italy under Ostrogothic rule.
Polities in southeastern Europe c.520 AD before the Lombard destruction of the Herulian 'kingdom'
Theoderic's efforts to build a system of alliances in Western Europe were made difficult both by counter diplomacy, for example between Merovingian Franks and the Byzantine empire, and also the arrival of a new Germanic people into the Danubian region, the Lombards. The Herule king Rodulph lost his kingdom to the Lombards at some point between 494 and 508.
After the Herulian kingdom was destroyed by the Lombards, Herulian fortunes waned. Some remaining Herules joined the Lombards and others moved into the old territory of the Gepids, and/or into areas where some defeated Rugii had moved after 488. According to Procopius many of the royal family with fellows went north and settled in "Thule" (the Scandinavian Peninsula) which corresponds to the envoy in 548 above and below .Others were moved into the northern Balkans, and came under East Roman authority. Anastasius Caesar allowed them to resettle depopulated "lands and cities" in the empire in 512. Modern scholars debate whether they were moved then to Singidunum (modern Belgrade), or first to Bassianae, and to Singidunum some decades later, by Justinian. In any case it appears that Justinian intended to integrate them into the empire as a buffer between the Romans and the more independent Lombards and Gepids to the north. The Herules were often mentioned during the times of Justinian, who used them in his extensive military campaigns in many countries including Italy, Syria, and North Africa. Pharus was a notable Herulian commander during this period. Several thousand Herules served in the personal guard of Belisarius throughout the campaigns, and Narses also recruited from them.
Procopius related that some the Herules who had been settled in the Roman Balkans killed their own king and, not wanting the one assigned by the emperor, they made contact with other Herules who had gone north instead after the defeat, seeking a new king who then arrived from Thule. Their request was granted, and a new king arrived with 200 young men - this was the envoy mentioned in the chapter "Origins".
Procopius, who did not like the Herules, said that after the succession dispute involving Justinian, some joined the Gepids and some remained loyal to Constantinople. In 549, when the Gepids fought the Romans, Herules fought on both sides. In any case after one generation in the Belgrade area, the Herulian federate polity in the Balkans disappears from the surviving historical records, apparently replaced by the incoming Avars.