К концу IV — началу V в. гунны сумели создать обширный союз племен, куда вошли многие народы Юго-восточной Европы: остроготы, гепиды, скиры, герулы, аланы» славяне. По всей видимости, эти народы продолжали находиться под управлением своих вождей, но платили гуннам дань и были обязаны по приказу гуннских правителей посылать в их распоряжение военные отряды.
Из сообщений древних авторов мы знаем о нескольких крупных гуннских вождях периода становления гуннской государственности: Баламбере, Басихе и Курсихе, Ульдине, Харатоне, Уптаре (Октаре) (см. главу 12). Последний правил гуннами вместе со своим братом по имени Руга (Руа, Ругила). В то время гуннский племенной союз уже представлял из себя очень значительную военно-политическую силу, с которой должны были считаться обе Римские империи — Западная и Восточная (Византия). С 422 г. Византия была вынуждена выплачивать гуннам ежегодную дань, размер которой постоянно увеличивался. В 433 г. правительство Западной Римской империи было вынуждено предоставить гуннам для поселения провинцию Паннонию.
Уптар, видимо, возглавлял западную часть гуннской державы, которая включала в себя земли к западу от Карпат и охватывала Великую Венгерскую равнину (Альфельд), тогда как Руга осуществлял контроль над территорией на востоке — степями Северного Причерноморья — главным оплотом военной мощи гуннов, их основной военной базой. После смерти Уптара около 430 г. во время похода против бургундов Руга стал единственным правителем гуннского племенного союза. В 434 г. умирает уже сам Руга, и ему наследуют его племянники, дети его брата Мундзука (Мундиуха) — Бледа и Аттила. Первый, более старший по возрасту, очевидно, унаследовал восточную часть государства, тогда как Аттила — его западные земли, где ранее управлял Уптар. Когда в 30-е гг. V в. жившие на Рейне бургунды попытались расширить свои владения за счет римской провинции Бельгики, то западноримский полководец Аэций призвал на помощь гуннов и с их помощью разбил бургундов (437 н. э.), причем тогда погибло великое множество людей из этого германского племени, включая короля Гундахара. Это страшное событие легло в основу созданного позже древнегерманского эпического цикла под названием «Песни о Нибелунгах» — предания о войнах между бургундами и гуннами. Так Аттила сумел посчитаться за гибель своего дяди Уптара и его воинов от рук тех же бургундов примерно 7 годами раньше,
В 444 или 445 г. Аттила убил Бледу и сделался единовластным государем, не только самым известным в гуннской истории, но и одним из известнейших персонажей в истории всего человечества. До нас дошло описание его личностных качеств и внешности:
Был он мужем, рожденным на свет для потрясения народов, ужасом всех стран, который, неведомо по какому жребию, наводил на все трепет, широко известный повсюду страшным о нем представлением. Он был горделив поступью, метал взоры туда и сюда и самими телодвижениями обнаруживал высоко вознесенное свое могущество. Любитель войны, сам он был умерен на руку, очень силен здравомыслием, доступен просящим и милостив к тем, кому однажды доверился. По внешнему виду низкорослый, с широкой грудью, с крупной головой и маленькими глазами, с редкой бородой, тронутой сединою, с приплюснутым носом, с отвратительным цветом [кожи], он являл все признаки своего происхождения.
