Переговоры с ромеями зашли в тупик. Юстиниан исправно выплачивал Баяну субсидии, но не изменял позиции в отношении перехода через Дунай. Так обстояли дела, когда в ноябре 565 г. император ромеев скончался. На престол вступил куропалат Юстин, сторонник жесткости по отношению к «варварам». 21 ноября к императору, лишь неделю назад взошедшему на престол, явились аварские послы, добиваясь выплаты положенной ежегодной «дани». Разгромившие союзников ромеев — антов и утигур, — усилившие себя за счет старых врагов Империи кутригур авары дерзко заявили: «Из ваших соседей мы разом истребили варваров, постоянно грабивших Фракию, и никого из них не осталось для набегов на фракийские пределы. Ибо боятся они силы авар, дружественно относящихся к державе ромеев». Возможно, конечно, что страх перед аварами сдерживал словенские набеги. Но следует помнить, что, за исключением устроенного Заберганом похода 559 г., словене с 552 г. не нападали на Империю ни разу. Авары тут были совершенно ни при чем. К тому же в Империи прекрасно помнили о гуннском набеге 562 г., совершенном самое меньшее при попустительстве Баяна.

Как бы то ни было, Юстин II не потерпел наглости «варваров». Человек вспыльчивый и решительный противник задабривания авар, он обрушился на послов с угрозами и площадной руганью, велел взять их под стражу, а затем прогнал без всяких денег. С дипломатией между Империей и аварами, по сути, было кончено. Коварный Баян, впрочем, не преминул заверить нового императора в своей «дружбе». Но он уже принял решение действовать помимо Империи и против ее интересов. Справедливости ради надо отметить, что иного выхода у кагана не оставалось. В 566 г. Истеми одержал победу над эфталитами в Средней Азии. Затем тюрки одновременно напали на Иран и вторглись в европейские степи. Им покорились оногуры, хазары и некоторые другие племена.

Баян не мог медлить. В том же 566 г. основные силы аварской орды во главе с самим каганом двинулись на север. Об этом походе судить можно лишь по косвенным данным. Баян шел вдоль Карпат, через земли дезорганизованных и отчасти порабощенных антских племен. Тех из антов и словен, кто остался враждебен аварам, каган сгонял с насиженных мест. Среди них были не только сербы и хорваты, но и какие-то словенские племена. К западу от Западного Буга авары потеснили или изгнали часть словен-лендзян. Очевидно, что аварское нашествие привело в движение очень многие славянские общины региона. Это и стало толчком к заселению славянами в конце 560-х — начале 570-х гг. значительной части современной территории Польши, а затем и Восточной Германии.

Надо думать, что столкновений с подкарпатскими группами словен (чехами, вислянами и др.) Баян по возможности избегал, не желая растрачивать силы. Свой удар он направил в уже разведанном в 561 г. направлении. В 566 или 567 г. каган появился у границ Тюрингии. На этот раз Сигиберт потерпел от «гуннов» поражение и сам попал в плен. Но Баян с самого начала не собирался глубоко вторгаться во владения франков и начинать большую войну. Он принял от пленника выкуп, заключил с ним договор о «вечной дружбе» и отпустил его восвояси с дарами.

Таким образом, заручившись договором с франками, Баян вдоль их границ спустился к Дунаю. В 567 г. авары форсировали реку и вошли в Паннонию с севера. Лангобардский король Альбоин (561–572), сын Авдуина, предпочел заключить с ними союз. Застарелая вражда лангобардов и гепидов с приходом авар наконец подошла к развязке. Альбоин в союзе с новыми пришельцами разгромил и уничтожил гепидское королевство. Часть гепидов признала власть Альбоина, часть — Баяна. По условиям заключенного между победителями договора, Альбоин уступал аварам Паннонию в обмен на помощь в борьбе против ромеев. Король лангобардов повел своих подданных в поход на Италию. Перед этим он принял арианство, разрывая последнюю связь с Империей. В 568 г.