В течение следующих двух лет Теодорих, сын Теодемира, со своими людьми рыскал по всему Балканскому полуострову от Диррахия до Константинополя, грабя и сжигая те районы Македонии и Фракии, которые раньше избежали разрушительных действий гуннов Аттилы и остготов предыдущего поколения. Военачальникам Зенона, пытавшимся его остановить, везло редко. Единственный успех, которого ему удалось добиться, — это победа в 480 году некоего Сабиниана, которому удалось окружить арьергард войска Теодориха, когда готы переходили Албанские горы, и захватить 2000 повозок и 5000 пленных. Но Сабиниана слишком боялся сам Зенон, которого подозревал в предательстве и потому в следующем году казнил. Только в 483 году Амал, разоривший Фракию и Македонию настолько полно, что даже его армия больше не могла найти там пропитания, наконец договорился с Зеноном. Сам Теодорих стал военным магистром, а для своего племени он получил дополнительные земли в Мезии и Дакии. Сын Триария умер годом раньше: он снова поднял мятеж против императора и уже собирал армию на фракийском побережье, когда погиб очень странной смертью. Норовистая лошадь сбросила его прямо на копье, которое стояло у его палатки, и то пронзило ему сердце. Его сын продолжил дело отца, но Теодорих Амал, не желавший терпеть других готских вождей на Балканском полуострове, кроме себя, убил юношу и включил его воинов в основной отряд остготов.
Полная беспомощность, которую Зенон продемонстрировал во взаимоотношениях с двумя Теодорихами, по-видимому, в значительной степени объясняется домашними проблемами. В 479 году, когда он не оказал поддержки Теодориху Амалу на Балканах, его трон зашатался и едва не рухнул из-за восстания в Константинополе. Марциан и Прокопий, два сына Антемия, покойного императора запада, популярные среди жителей столицы, устроили заговор, направленный на свержение императора. Они привлекли на свою сторону многих значительных людей. Они сумели ворваться во дворец и убить телохранителей, но Зенону удалось бежать, привести преданных ему исаврян из Азии и подавить восстание после ожесточенных уличных боев. В 482–483 годах он разошелся во мнениях с исаврийским военачальником Иллом, который пятью годами ранее подавил восстание Василиска. Зенон не мог изгнать его, но не доверял. Он оставил его в должности, но постоянно оставался настороже и всячески ему мешал. Говорят, что императрица Ариадна попыталась организовать убийство Илла — с согласия императора или нет, точно неизвестно. В 483 году, когда Теодорих Амал помирился с Зеноном, некто Леонтий поднял восстание в Сирии. Иллу, который был послан на подавление восстания, надоело служить неблагодарному и подозрительному хозяину, и он присоединился к восстанию. Он и Леонтий захватили Антиохию, где последний был провозглашен императором, а также овладели Каппадокией, Киликией и севером Сирии. Утверждают, что они намеревались вернуть язычество — проект, который представляется совершенно невероятным в конце V века, когда язычников уже почти не осталось. Вдовствующая императрица Верина, жившая в Каппадокии, присоединилась к ним и даже усыновила Леонтия. Мятежники также приняли более практические меры для поддержки своего дела. Они обратились к Одоакру, королю Италии, и персидскому монарху Балашу. Оба пообещали помощь, но не успели ее отправить. Зенон сумел подавить восстание раньше. Он убедил своего прежнего врага Теодориха присоединиться к его армии. Готы и исавряне вместе легко одержали верх над Леонтием. Сирия покорилась. Мятежный император и его военачальник Илл после долгой отчаянной обороны в замке Каппадокии были схвачены и убиты.
После подавления восстания Леонтия Зенон некоторое время наслаждался миром. В 488 году он уговорил Теодориха Амала повести остготов из Мезии на завоевание Италии. Как Теодорих показал себя в Италии, мы уже рассказывали. Его уход оказался благом для империи. Впервые после восхождения на престол Зенон получил реальную власть над своими европейскими провинциями. Они были оставлены в ужасном состоянии. Десять лет войны, свирепствовавшей на всей территории, что к югу от Дуная и к северу от горы Олимп, превратили землю в пустыню. Целые регионы полностью лишились населения. Наличие столь обширных свободных территорий манило на Балканский полуостров новых врагов. На севере Балкан было уничтожено почти все провинциальное население. Когда остготы покинули эту территорию, между горами и Дунаем не осталось практически ничего, за исключением нескольких военных гарнизонов. Население здесь так и не появилось, пока сюда не пришли славяне в следующем веке. В Иллирии и Македонии дела обстояли не так плохо. Однако общим результатом столетия готской оккупации Балканского полуострова стало катастрофическое уменьшение латиноязычного населения Восточной империи. Жители внутренних территорий Фракии, Мезии и Иллирика до этого в основном использовали латинский язык. Когда их стало меньше, империя стала более азиатской и греческой, чем была раньше.