Not long after the battle at the Nedao the old rivalry between the Gepids and the Ostrogoths spurred up again and they were driven out of their homeland in 504 by Theodoric the Great.
Njihov prvi znani kralj je bil Fastida, ki je z vojsko razširil meje svojega kraljestva in v 4. stoletju podjarmil in skoraj iztrebil Burgunde.