The Vikings came centuries after the end of the Western empire, and first start to be noted as a distinct cultural phenomenon in the 8th century.
The exact origin of the term is still debated, but it was used among Norse speakers to denote those who subscribed to the particular wide-ranging seagoing lifestyle we're familiar with. It didn't always necessarily imply raiding and pillaging, but that aspect of it is what came most strongly to the attention of neighboring peoples who called them variously Danes, Northmen, Rus, and Varangians, among other things.
The Viking phenomenon appeared toward the end of a period often called "the Migration Age," during which numerous Germanic-speaking tribal groups expanded into new territories throughout Europe and even as far as North Africa, where the Vandals set up a short lived empire. The beginning of the Migration Age coincides with the death throes of the Western Empire, and those two currents of history are strongly related to one another. The earlier groups, Franks, Vandals, Goths, Saxons, etc. are not usually referred to as Vikings, though their cultures had some similar traditions.
The highly developed mythology that we usually call Norse was mostly recorded toward the end of or even after the time of the Vikings (and after Christianization), and so it may not even accurately represent the Viking worldview, much less those of earlier peoples.
On the other hand, at least some of Norse mythology certainly reflects earlier traditions. Evidence of characters corresponding to several of the gods, Thor, Tyr, Freya, and Odhin particularly, can be seen at least back to the 6th century, and Tacitus in the 1st century notes some customs and beliefs among continental Germanic tribes which are fairly clearly related to some we see in the sagas.
However, it is clear that there were some major developments, many of them quite regional, over the millenium between Tacitus and Sturluson. The so-called Odinic cult that colors the Eddas so strongly probably developed long after Tacitus for example, and one cult idea which we know from archaeology to have been centrally important in the time of the Roman Empire, the three Deae Matres, only shows faint traces in Viking and post-Viking belief.
Confusing the issue, many tribes, lacking a written tradition, easily took up foreign ideas and quickly began to think of them as their own while they wandered around the Empire looking for better opportunities. The later Goths in particular were so heterogeneous in their ethnic makeup and so well travelled that it's difficult to know what to make of the scattered references to their pre-Christian beliefs.
Scandinavia itself before the Viking period is poorly known to history, though there are a few odd and fairly interesting notes on the region in Tacitus and a few other sources. Tacitus did give some Scandinavian tribal names that appear to correspond to some known later, so what he says can't be entirely dismissed as fantasy, but it's likely to be a little distorted.
-Neither a Viking Nor an Expert
from swedish historical times
