Несмотря на это поражение, гунны оставались чрезвычайно важным элементом событий того времени. Те же Базих и Курзих через какое-то время появляются в Риме и заключают союз с западным императором Гонорием. Теперь главным объектом их нападений становится Балканский полуостров. В 400 г. предводитель готских наемников Гайна поднял мятеж и попытался захватить Константинополь. Он был разбит и ушел на левый берег Дуная. Однако константинопольское правительство не оставило его в покое. Следуя своей ставшей обычной практике, оно возбудило против Гайны гуннского предводителя Ульдина. Ульдин, с одной стороны, понимая, что в данном случае ему лучше договорится с римлянами, а с другой, боясь, что Гайна сможет использовать свои войска для создания своего государства, выступил против него. После нескольких сражений Гайна был убит и обезглавлен. Его голову Ульдин переслал Аркадию. Возможно, при этом было заключено какое-то соглашение, предусматривавшее оказание гуннами помощи римским войскам в случае необходимости. Такая помощь вскоре, действительно, понадобилась, но не Восточной, а Западной империи, когда в 406 г. готы Радагайса вторглись в Италию. Гунны под руководством Ульдина соединились с частью готов, которые под командованием Сара служили римлянам, и сыграли большую роль в разгроме Радагайса. Может быть, Стилихон, фактически правивший Западной Римской империей, после этого уступил Ульдину провинцию Валерию (часть Паннонии). Если это так, то было это сделано не только в благодарность за помощь, но и с целью оказать большее давление на восточное правительство, поскольку уступленная гуннам провинция находилась у самых границ этой части Империи. В таком случае впервые гуннам была подчинена часть территории Империи. Какая-то часть гуннов осталась на службе у Стилихона, войдя в состав его личной гвардии[61].
В 408 г. умер восточный император Аркадий и на престол вступил его малолетний сын Феодосий II. Стилихон пытался воспользоваться сменой власти в Константинополе и воплотить в жизнь давнюю мечту об объединении всей Империи фактически под своей властью. Эго ему не удалось, и не исключено, что он подтолкнул Ульдина на вторжение в Восточную империю. Первую попытку вторгнуться на территорию этой империи Ульдин предпринял еще в 404–405 гг., несмотря на недавно заключенный договор. Теперь вторжение было повторено в еще большем масштабе. К этому времени Ульдин подчинил себе и других варваров, живших к северу от Дуная. Среди них были скиры. С объединенной армией гуннов и скиров Ульдин перешел Дунай и стал разорять Мезию и Фракию. Возглавлявший константинопольское правительство префект претория Антемий, понимая, что сил справиться со всем войском Ульдина у римлян мало, прибег к интригам, включая элементарный подкуп. В результате этих интриг ряд подчиненных Ульдину гуннских и, по-видимому, скирских вождей с их отрядами перешли на сторону римлян. После этого справиться с оставшимися войсками Ульдина было уже легче. В первые месяцы 409 г. произошло несколько сражений. Гунны, как кажется, не были разбиты, но их потери были столь велики, что оставаться дальше на римской территории они уже не могли. Сам Ульдин с трудом избежал гибели. Остатки своей армии он увел на левый берег Дуная. После этого об Ульдине ничего неизвестно. Важно отметить, что древние авторы, говоря об Ульдине. не называют его королем, но лишь предводителем (гегемоном). Словом «гегемония» определяется и его власть над другими варварами. Возникает вопрос: может быть, Ульдин не принадлежал к королевскому роду и властвовал над частью гуннов de facto, а не de jure? В 412–413 гг. «первым из гуннских королей» был, как уже говорилось Харатон. Каково его отношение к Ульдину — неизвестно.