At the time of their accession, the Huns were bargaining with Byzantine emperor Theodosius II's envoys over the return of several renegade tribes who had taken refuge within the Roman Empire.

Their advance began at Margus, for when the Romans discussed handing over the offending bishop, he slipped away secretly to the Huns and betrayed the city to them.

Theodosius had stripped the river's defenses in response to the Vandal Gaiseric's capture of Carthage in 440 and the Sassanid Yazdegerd II's invasion of Armenia in 441.

A lull followed in 442, and, during this time, Theodosius recalled his troops from North Africa and ordered a large new issue of coins to finance operations against the Huns.

They encountered and destroyed the Roman force outside Constantinople and were only halted by their lack of siege equipment capable of breaching the city's massive walls.

Theodosius admitted defeat and sent the court official Anatolius to negotiate peace terms, which were harsher than the previous treaty: the Emperor agreed to hand over 6,000 Roman pounds (ca.

1,963 kg) of gold as punishment for having disobeyed the terms of the treaty during the invasion; the yearly tribute was tripled, rising to 2,100 Roman pounds (ca.

According to Jordanes (following Priscus), sometime during the peace following the Huns' withdrawal from Byzantium (probably around 445), Bleda died (killed by his brother, according to the classical sources), and Attila took the throne for himself.

And the first king of Scythia was Magog, son of Japhet, and his people were called Magyars [Hungarians] after their King Magog, from whose royal line the most renowned and mighty King Attila descended, who, in the 451st year of Our Lord's birth, coming down from Scythia, entered Pannonia with a mighty force and, putting the Romans to flight, took the realm and made a royal residence for himself beside the Danube above the hot springs, and he ordered all the old buildings that he found there to be restored and he built them in a circular and very strong wall that in the Hungarian language is now called Budavár [Buda Castle] and by the Germans Etzelburg [Attila Castle]