The Heruls are first mentioned by Roman writers in the reign of Gallienus (260 - 268), when they accompanied the Goths ravaging the coasts of the Black Sea and the Aegean. The mixed warbands managed to sack Byzantium in 267, but their eastern contingent was virtually annihilated in the Balkans at the Battle of Naissus (Serbia) two years later, the battle that earned Marcus Aurelius Claudius his surname 'Gothicus.' A western contingent of Heruli are mentioned at the mouth of the Rhine in 289.
By the end of the 4th century the Heruls were subjugated by the Ostrogoths. When the Ostrogothic kingdom of Ermanaric was destroyed by the Huns in about 375, the Heruls became subject to the Hunnic empire. Only after the fall of the Hunnic realm in 454, were the Heruls able to create their own kingdom in southern Slovakia at the March and Theiss rivers.
After this kingdom was destroyed, however, Herulian fortunes waned. Remaining Heruls joined the Langobards and moved to Italy, and some of them sought refuge with the Gepids. Marcellinus comes recorded that the Romans (meaning the Byzantines) who allowed them to resettle depopulated "lands and cities" in Moravia, near Singidunum (Belgrade); this was done "by order of Anastasius Caesar" sometime between June 29 and August 31, 512 CE. After one generation, this minor federate kingdom disappeared from the historical records.
Records indicate, however, that the Heruli served in the armies of the Byzantine emperors for a number of years, in particular in the campaigns of Belisarius, when much of the old Roman territory, including Italy, Syria, and North Africa was recaptured. Several thousand Heruli served in the personal guard of Belisarius throughout the campaigns. They disappear from historical record by the mid-6th century.
According to Procopius, many Heruli returned to Scandinavia and settled beside the Geats (Gautoi). The places where they are assumed to have resettled have been identified with Vermland or the provinces of Blechingia and Värend, two districts where the women had equal rights of inheritance with their brothers. Some noble Swedish families in the area also claim to be descendants of the returning Heruli. It should be noted that such identifications are not widely accepted.
No "Heruli" are mentioned in Anglo-Saxon, Frankish or Norse chronicles, so it is assumed they were known in the north and west by another name. Encyclopædia Britannica 1911 suggested that, since the name Heruli itself is identified by many with the Anglo-Saxon eorlas ("nobles"), Old Saxon erlos ("men"), the singular of which (erilaz) frequently occurs in the earliest Northern inscriptions, that "Heruli" may have been a title of honor.
From the end of the 3rd century, Heruls are also mentioned as raiders in Gaul and Spain, where they are mentioned together with Saxons and Alamanni. These Heruls are usually regarded as Western Heruls; their settlements are assumed to have been somewhere at the lower Rhine.