They were first clearly recorded by Tacitus, in his Germania who called them the Rugii, and located them near the south shore of the Baltic Sea. Some centuries later, they were considered one of the "Gothic" or "Scythian" peoples who were located in the Middle Danube region. Like several other Gothic peoples there, they possibly arrived in the area as allies of Attila until his death in 453. They settled in what is now Lower Austria after the defeat of the Huns at Nedao in 454.
The Baltic Rugii mentioned by Tacitus are possibly related to the people known as the Rutikleioi, and the place known as Rougion, both mentioned in the second century by Ptolemy. Both these names are associated with the coastal island known today as Rügen. They have also been associated with the Ulmerugi mentioned in the 6th century by Jordanes, as people who had lived on the Baltic coast near the Vistula long before him. In a passage that is difficult to interpret Jordanes mentioned that the Rugii also lived in Scandinavia in his own time, near the Danes and Suedes.
It has been speculated, based on their name, and the Gothic origin stories published by Jordanes, that the Rugii originally migrated from southwest Norway to Pomerania around 100 AD, and from there to the Danube River valley. The name of the Ulmerugi has been interpreted as Holmrygir known from much later Old Norse texts. The Rugii have also been associated with the Rygir of Rogaland in Norway. All these names apparently share their etymological origins.