Around 522, the Avars lost their dominant position in Central Asia. Fleeing their Turkic enemies, and accompanied by their allies, the Hephtalite Huns, they reached the northern approaches of the Caucasus at the end of 557. The following year, in Constantinople, Avar envoys negotiated a treaty of alliance with Emperor Justinian and obtained a grant of gold. They agreed, in exchange, to attack and subjugate some tribes in Southern Russia and in Ukraine — the Sabirs, Utigurs, Kutrigurs, and Saragurs — which had been draining the empire's treasury. Within three to four years, the Avars accomplished the task of (in their own words) 'wiping them off the face of the earth'.

In 562, the Avars reached the Lower Danube. Their leader, the Kagan Bayan ('bayan', meaning 'powerful, rich', was also used as a personal name) once again dispatched envoys to Justinian: the Avars now demanded renewal of the treaty, a higher annuity, and land suitable for settlement. Bayan had set his sights on the plain lying to the south of the Lower Danube, and protected by that broad river; it encompassed Scythia Minor and Moesia (Dobrudja and Northern Bulgaria), the same regions that the Bulgar Turks would occupy a century later. However, the Eastern Romans had just sealed off their frontiers, ruling out any such concession to the Avars. Thereupon, the Avar forces advanced around the northern Carpathians, only to be halted in 563, at the Elbe, by Sigebert, the Frankish King of Austrasia. They were thus compelled to return to 'Scythian Danube', the Lower Danube region, where, on Bayan's orders, 'the tents were raised in a dense mass on the broad plain'.[13]13. Corippus, In laudem Iustini III.

The Avars did not tarry when they learned that Justinian I had died on 21 November 565; within a week, their envoys were in {1-219.} Constantinople. In the 'insistent tone' that marked the nomads' diplomacy, they demanded that the new emperor renew the alliance. Instead, Iustinus II abrogated the treaty, indicated (in a similarly arrogant tone) that he would no longer pay the 'servants' wages', and declared that the Lower Danubian frontier would remain sealed. In the winter of 565–66, the Avars made an attempt to force their way through, but failed.

Almost as if they were trying to escape from a trap, the Avars once again circled the Carpathians, and reached Thuringia in the fall of 566. Although they prevailed on the battlefield against Sigebert's forces, the outcome was a truce and the withdrawal of both armies.

The Avars' desperate attempts to break through on the Lower Danube and, twice, to get around Carpathians, were driven by a real sense of danger, and that danger became more immediate in the winter of 566–67. In pursuit of their 'subjects', the Western Turks had crossed the Volga and, coming within striking distance, threatened to kill the Avars 'not with swords but with the hooves of their horses, by treading them into the ground like ants'. It is clear that the Avars, having suffered five years of adversity, yearned for a haven behind defensible natural boundaries — if not on the Lower Danube, then on the plain enclosed by the Carpathian Mountains; yet neither option proved to be attainable. Historical and archaeological sources confirm that the Avars could find no passage through the Northern and Eastern Carpathians.

The archaeological data on settlements in the 5th and 6th centuries indicate that along the Northern and Eastern Carpathians, an uninhabited and uninhabitable forest had spread in a swath that was, on average, some 120 kilometres wide (and as much as 150–200 kilometres wide in certain areas). For an entire people and its livestock, this zone would have been virtually impassable even if it had not included, in the middle, a 80–100 kilometre-wide mountain barrier with an altitude ranging from 1500 to 2000 {1-220.} metres. The situation in Transylvania could be extrapolated from the valleys of the Upper Tisza and Lower Szamos rivers: from the beginning of the 6th century, there is no archaeological trace of human life in that region all the way to the Tiszafüred-Nyíregyháza-Debrecen line. In that period, a people intent on migrating would be limited to a few more or less accessible passes in the Southern Carpathians, principally the Vöröstorony (Rotenturm) Pass, in the Olt valley, and the Roman-built roads (later used by Gepidic forces) along the Lower Danube. However, these routes were barred by the Gepids' and Byzantines' strong military outposts.

The Avars were truly caught in a trap, for if they were still in the Lower Danube region when the Turks caught up with them, they faced slaughter. These fears had not entirely dissipated even twenty years later, when they lived in the Carpathian Basin (much like the Hungarians' lingering fear of the Pechenegs around 920); in 580, Emperor Tiberius II tried to make them lift the siege of Sirmium by spreading the (false) news that Cherson had been captured by the Turks.

In the critical days during the winter of 566–67, emissaries of the Langobard King Alboin met with Bayan somewhere between the Elbe and Oder rivers; Sigebert, Alboin's brother-in-law, had probably acted as mediator between the two powers. The envoys proposed a joint, two-front assault on the Gepids, as well as an 'eternal alliance' ('foedus perpetuum', which in Langobard usage signified a military alliance).[14]14. Paulus Diaconus, Historia Langobardorum I, p. 27. They accepted Bayan's demand that, in the event of victory, the Gepids' land, population, and riches be given to the Avars; they even evoked the tempting prospect that the Avars, if they captured Pannonia Sirmiensis, might easily cross the Sava River and realize their dream of occupying Scythia Minor and Thrace, or indeed press on all the way to Byzantium.

Few details of the famous joint operation survive, for the Langobards were more intent on recording their own achievements. {1-221.} It is likely that, in keeping with the terms of the agreement, the assault was launched by the Langobards. The Gepid King Kunimund drew together his forces 'from several directions'[15]15. 'e diverso', Historia Langobardorum I, p. 27. to meet the Langobard attack. Only after he had taken this fateful step did he learn of a second, Avar attack (Tristis ad Cunimundum nuntius veniens, invasisse Avares). As a result of the strategy that had been agreed upon with Alboin ('ut cum Alboin statuerunt'), the Avar army (it must be emphasized that what happened was an attack by Avar forces, and not a 'migration' of the Avar people) was able to break through the sealed frontiers (terminos edicit).

Bayan's ultimate objective was Sirmium; at the original negotiations, he already requested that Langobards provide guides who could lead him against Sirmium. Moving in through the Moravian Pass and along the left bank of the Danube, 'taking immense pains and covering a long distance,' he set upon the Gepids. The late Langobard chronicles naturally attribute to their own king and people the glory of defeating the Gepids. But Byzantine contemporaries, who were well-informed and had a direct interest in the matter, recorded that it was Bayan who had 'defeated them in war' and 'smashed the Gepids' state'.[16]16. Menander Protektor, Excerpta..., 195, 458. They were undoubtedly right; on this occasion, the Langobards had played but a secondary role and reaped the benefits of their allies' sweeping success.

Thus Bayan defeated the Gepids' main force, led by King Kunimund; the latter was killed in battle, and Bayan, in keeping with ancient Eastern custom, had his opponent's skull turned into a drinking bowl before presenting it — ostensibly in friendship — to Alboin. Thereupon, Bayan immediately crossed the Danube to attack Sirmium's Gepidic defenders. The commander of the latter, Usdibad, did not wait for the Avars to arrive; he and his soldiers surrendered to the East Roman forces, who were on a state of alert. The Gepids' heir apparent, Reptila, fled to Constantinople, as did the head of the Gepid Arian Church, Bishop Thrasarik. By the time Bayan reached Sirmium, the town was already defended by {1-222.} Bonos's Byzantine troops; the latter repulsed the Avar cavalry, which was unprepared for the siege of a fortress.

In the meantime, the Langobard-Gepid war came to an end on the Great Plain as well. Kunimund's daughter, Rosamund, and her retinue were either taken into captivity by Alboin, or, perhaps, chose the lesser evil and sought refuge with Alboin. Thousands of Gepid warriors followed suit; indeed, in such numbers that four years later, while serving Queen Rosemunda in Italy, they were able to overthrow Alboin and imperil for several months the Langobard princes' grip over northern Italy. In the area between the Tisza, Maros, and Körös rivers, few Gepids remained who were capable of bearing arms.

After the setback at Sirmium, Bayan and his army crossed the 'Ister' river and occupied the Gepids' ransacked and plundered land.[17]17. Menander Protector, Fragmenta, p. 27. The source does not relate how the rest of the Avars followed suit to settle in their new homeland. They could not have taken the Vaskapu (Iron Gate)-Orsova Pass, for it was barred by a now openly hostile Byzantine fleet. The most likely route was through the Vöröstorony Pass and the valleys of the Olt and Maros rivers. Archaeological finds indicate that this route was in use both during the Avar period and in the 9th century.