Неудача антивандальской экспедиции 468 г. привела к гибели не только флота, но почти всего экспедиционного корпуса, основу которого составляла Первая презентальная армия Василиска. После провала этой экспедиции империя долго не могла восстановить численность личного состава своих армий. Считается, что к концу правления императора Льва (правил 457–473) была восстановлена сила только Первой презентальной армии, в то время как Второй презентальной армии практически не существовало до завершения финансовых реформ императора Анастасия. Значившиеся же поочередно по несколько лет в качестве ее командиров готские вожди Теодорих Косой, сын Триария, и Теодорих, сын Теодемира (будущий Теодорих Великий), фактически были почетными магистрами, использовавшими императорские средства (вначале по 2000 £Аu в год) для укрепления своей личной власти среди готов: сумма эта была достаточна для содержания войска более чем в 25 000 воинов.[62]

При императоре Зеноне (474–491), опиравшемся на клан своих исаврийских родственников, империя вела вялотекущие войны с готами на Балканах и с мятежными кланами в горной Исаврии. Эти войны носили характер скорее внутриполитических «разборок», чем настоящих планомерных кампаний по отражению внешнего врага. Интересен один эпизод из множества событий этой борьбы.

Война с готами началась с заключения в 478 г. договора императора с одним готским вождем против другого — с Теодорихом, сыном Теодемира, против Теодориха Косого[63]. По этому договору (Malch. fr. 15) римляне обещали поддержать готское ополчение Теодориха, сына Теодемира, бывшего в то время презентальным магистром. Теодорих должен был двинуться из окрестностей города Марцианополя против готов мятежного Теодориха Косого. У проходов через горный массив Стара-Планина на южной окраине провинции Нижняя Мезия к нему должен был присоединиться магистр Фракии с 10 000 тяжелой пехоты (hoplitais) и 2000 конницы. Позже у реки Гебр (совр. Марица) в районе Адрианополя должны были подойти еще 20 000 пехоты (pezous) и 6000 конницы, поддержанные другими частями из Гераклеи и округи Константинополя. Очевидно, это были силы Фракийского магистерия и Первой презентальной армии под командованием только что назначенного Мартиниана, а также какие-то палатинские схолы. Любопытно соотношение пехоты и конницы: 5:1 и 3⅓:1, соответственно[64]. Во-первых, несомненно преобладание пехоты над конницей (в таком же, примерно, соотношении, как и в римских армиях IV в.). Во-вторых, видно, что доля конницы в презентальной армии больше, чем во фракийской (что соответствует ее большей мобильности). Эти силы так и не присоединились к Теодориху и, возможно, точно в таком численном виде существовали только на бумаге. Однако договор все-таки включал в себя пункт, касавшийся этих двух армейских группировок, и их фактическая сила и соотношение родов войск не должны были слишком отличаться от приведенных величин:[65] Теодорих, наверняка, хорошо знал реальное положение дел в восточноримской армии, и в тексте договора могли присутствовать упоминания только реально существующих военных сил. Кроме того, другие факты говорят в пользу того, что в распоряжении Зенона на Балканах на этот момент должно было быть не менее 20–30 тысяч воинов мобильной армии. Действительно, вскоре Зенон решит начать активные военные действия сразу против обоих Теодорихов, при том что силы сына Триария составляли не менее 13 000 человек (на них он позже получит довольствие от императора). А ведь у Зенона, для того чтобы планировать активные военные действия, на Балканах не должно было быть заметно меньше сил, чем у обоих Теодорихов вместе взятых. Более того, можно предположить, что силы империи на востоке Балкан состояли точно не из готов. Так, известно, что командиры ряда балканских частей опасались оказаться в окружении не очень дружественных готов Теодориха и не присоединились к его войску, несмотря на приказ командования.

После этого оба готских вождя объединились в борьбе с Константинополем. И тогда Зенон стал готовиться к войне с ними, пообещав солдатам, что сам лично возглавит военные действия, что резко подняло боевой дух армии. Затем, однако, он так ничего и не предпринял, чем вызвал крайнее негодование среди солдат. Рост неприязни к Зенону был столь велик, что презентальный магистр Марциниан был вынужден поскорее распустить войска на зимние квартиры. Затем, после того как один из Теодорихов взял город Скупы, многие из находившихся там римских солдат отказались присоединиться к варварам, за что были все перерезаны готами. Все это вместе взятое указывает на высокий боевой дух этих римских частей. Итак, на востоке Балкан в 70-х гг. V в. у римлян была мобильная армия, организованная в соответствии с нормами IV в. и обладавшая традиционным римским духом. Численность этих сил, скорее всего, была ниже требуемой. На западе Балкан, в Иллирике, дела, возможно, обстояли несколько хуже — в частности потому, что магистр Иллирика скир Онульф, предав Зенона, увел с собой в 479 г. часть войск в Италию к своему брату Одоакру, захватившему власть в Западной империи за три года до этого. Назначенный на место Онульфа Сабиниан Магн имел вначале лишь небольшой отряд букцелляриев, в то время как оставшиеся после ухода Онульфа силы были разбросаны по укреплениям.[66]

При Зеноне по-прежнему все-таки ощущалась нехватка живой силы в войсках: видимо, старая система пополнения армии за счет рекрутского набора не оправдывала себя. Поэтому для создания крупных группировок приходилось сводить воедино войска различных магистериев — практика, которая позже разовьется при императоре Юстиниане. Так, в действиях против исавров в 475 г. Первый презентальный магистр Армат, предшественник Мартиниана, получил экстраординарные полномочия: его пост назывался «Великий презентальный магистр» (stratēlatēs tou megalou praisentou).[67] При этом он командовал не только войсками своего (Первого презентального) магистерия, но и отрядами схол и войсками фракийского и Второго презентального магистериев. Таким образом, фактически Первая презентальная армия была усилена в 475 г. за счет сил Фракийского магистерия и за счет тех сил Второй презентальной армии, которые уже смогли восстановиться после вандальской экспедиции.[68] Однако ясно, что оставить магистра Фракии полностью без войск было бы неразумно. Возможно, до 474 г. силы фракийского магистерия значительно превышали указанные выше 12 000. Восстановление численности фракийской армии после поражения от гуннов на р. Ута в 447 г. было осуществлено в общих чертах к 460 г.[69] В 484 г. магистр Фракии Леонтий будет послан со своим войском в Исаврию, что также указывает на наличие некоторых достаточных для этого сил.

Провозглашение императором Анастасия (491–518) после смерти Зенона привело к изгнанию всех исавров из Константинополя, что стало причиной семилетней войны с этими воинственными горцами.[70] Они смогли быстро собрать огромное ополчение в 100 000 человек. Против них в срочном порядке