A hunok Rua (Ruga, Rhuas) hadúr vezetésével 432-re egyesültek. 434-ben Rua meghalt, és unokaöccseire, Mundzuk testvére fiaira, Attilára és Bledára (*390 körül – †445) hagyta a hun törzsek irányítását.
Ebben az időben a hunok II. Theodosius császártól követelték a Bizánci Birodalomba menekült néhány „renegát” törzs kiadatását. A következő évben Attila és Bleda Margusnál (ma Pozsarevác) fogadta Bizánc küldöttét, és hun szokás szerint mindannyian lóháton ülve szerződést kötöttek: a keletrómaiak nem csak a menekült törzseket (akiknek jó hasznát vették a vandálok ellen) fordították vissza, hanem megduplázták 350 római fontnyi (kb. 114,5 kg) aranyra az adójukat (tribute), megnyitották a piacaikat a hun kereskedők előtt, és a hunok által ejtett valamennyi fogolyért 8 solidust fizettek váltságdíjként. A megállapodással elégedett hunok felszedték sátraikat, és visszavonultak a kontinens belső területeire, vélhetően a birodalmuk megerősítésére.
Theodosius felhasználta az alkalmat Konstantinápoly falainak megerősítésére, és felépítette a tenger felől védő első falat is, illetve a Duna-menti határa védvonalát is megerősítette. A következő öt évre a hunok eltűntek a római szemek elől, de 440-ben újra felbukkantak a birodalom határainál, megtámadva a szerződés alapján meglévő, a Duna északi partján működő piac kalmárait.
Attila és Bleda további háborúval fenyegetőzött, azt állítva, hogy a rómaiak nem tartották be a szerződést, továbbá Margus (a mai Belgrád melletti település) püspöke átkelt a Dunán, hogy megszentségtelenítse a hun királyi sírokat a Duna északi partján. A hunok a folyón átkelve nagy illír városokat és erősségeket romboltak le, köztük (Priscus szerint) Viminaciumot is A támadást Margusnál kezdték, mivel a püspök, akit a rómaiak átadni terveztek, titokban átszökött a barbárokhoz, és elárulta, feladta a városát.
Theodosius a folyómenti véderőit visszavonta, hogy válaszolhasson a 440-ben Karthágót elfoglaló vandál Geiserich (Geiseric, Gaiseric, Genseric) és az Örményországot 441-ben megszálló szaszanida II. Yazdegerd (Izdegerdes) támadásaira. Így Attila és Bleda előtt nyitva állt az út Illírián keresztül a Balkánra, amit 441-ben el is özönlöttek. A hun sereg megsarcolta Margus és Viminacium városát, elfoglalta Sigindunumot (a mai Belgrádot) és Sirmiumot. Fordulat állt be 442-ben, amikor Theodosius kivonta a csapatait Észak-Afrikából, és nagy mennyiségben új pénzt veretett a hunok elleni hadjárat finanszírozására.
Attila és Bleda válaszul 443-ban újraindította a hadjáratát. A Duna mentén haladva legyőzték Ratiara katonai központjait és sikeresen megostromolták Naissus városát (a mai Ništ). A Nisava mentén előrenyomulva elfoglalták Serdica (Szófia), Philippopolis (Plovdiv) és Arcadiopolis városát. Konstantinápolynál körbefogták és megsemmisítették a római erőket, és csupán azért kényszerültek megállásra, mert a város masszív falaihoz nem volt megfelelő ostrom-eszközük. Theodosius elismerte a vereséget, és Anatoliust küldte a béketárgyalásra, amely a korábbiaknál is keményebb volt: a császár átad 6 000 római fontnyi (kb. 1963 kg) aranyat, büntetésül a korábbi egyezség megszegéséért, az éves adót megháromszorozza, így az 2 100 font arany lesz (kb. 687 kg), és minden egyes hadifogolyért 12 solidus váltságdíjat fizet.
A sikeres hadjárat után a hunok visszahúzódtak birodalmuk belsejébe. A Priscust követő Jordanes írása szerint nem sokkal a távoztuk után, 445 körül Bleda meghalt, és Attila maga ült a trónra. A történészek vitáznak azon, hogy vajon megölte-e a bátyját egy vadászaton, vagy az más okból halt meg, de Attila vitathatalan ura lett a hunoknak, akik ismét a Keletrómai Birodalom felé fordultak
