Такие обширные завоевания стали возможными благодаря грандиозной программе реформ Юстиниана, затронувших среди прочего и военную сферу. В армии были проведены значительные реформы: роль презентальных армий была постепенно сведена к минимуму, их численный размер существенно сократился, и для формирования крупной походной армии теперь стягивались войска различных региональных магистериев во главе с их магистрами. В результате во время больших завоевательных кампаний большинство региональных войск с их магистрами подолгу отсутствовали в своих регионах. Поэтому охрана границ ослаблялась, т. к. сил одних лимитанов для отвращения врага часто бывало недостаточно. Для предотвращения часто возникавших при этом в походной армии конфликтов между различными магистрами был введен институт назначаемого императором полномочного полководца или стратига-автократора. В глазах современников различие между презентальными и региональными войсками свелось лишь к местам их расквартирования — в регионах (Фракии, на севере Иллирика, Армении или Месопотамии) или же в столице: и те и другие называются теперь просто «воинами (греч. stratiōtai) из Византия» или же «воинами из Илллирика». Все же вместе назывались или просто «воинами, состоящими в списках» (греч. stratiōtai ek katalogou), или «пехотинцами…» (греч. pezoi…) и «всадниками, состоящими в списках» (греч. hippeis ek katalogou), или же «вексилляциями перечисления» (vexillationes arithmou). При этом все они противопоставлялись другой части походного войска — федератам. Общая численность воинов походной армии (презентальных и региональных вместе) Восточной империи на начало V в. примерно определяется исследователями в 100 000 человек. На середину VI в., по сведениям Агафия — историка того времени, армия империи насчитывала 150 000 человек, но не до конца ясно, включал ли он в это число также и численность лимитанов. Примерная нормативная численность каждой из презентальных армий была 25 000—30 000, а региональной — 15 000—20 000 человек, что в сумме и должно дать чуть больше ста тысяч для территории Востока империи.
Общий мир, установившийся на основных территориях империи к началу 50-х гг., был прерван только в 559 г. нашествием гуннов-кутригуров под руководством их царя Заберагана зимой — летом 559 г. Набег был хотя и единственным за этот период, но столь неожиданным, что привел руководство империи к полному замешательству. Оказалось, что спустя каких-то пять — семь лет после побед Нарзеса в Италии у империи нет войск для обороны даже самой столицы. Константинополь чудом и лишь по неведению врага избежал захвата Заберганом. Почему у империи не оказалось войск вблизи столицы в этот момент — было неясно еще современникам. В 558 г. у границ империи появились новые пришельцы из глубин Центральной Азии — авары. Вскоре (в 562 г.) они попытались померяться силами с империей на Нижнем Дунае, но пока сила была не на их стороне. В целом спокойная общая обстановка этих лет и военная слава империи не требовали более держать войска в постоянной военной готовности. Это и старость императора привели к тому, что военное дело и армия оказались в небрежении, а международные дела решались— пока еще успешно — исключительно дипломатическими мерами и денежными дарами, как бы за счет прошлых побед.
При преемнике Юстиниана его племяннике Юстине II (565–578) империя резко изменила тон отношений с соседями: император на седьмой же день своего правления отказал в денежных выплатах аварским послам. Снова была сделана ставка на силу, однако Юстин, не будучи человеком военным, видимо, недооценивал реальное положение в армии. Последствия не замедлили себя ждать. Вначале авары, объединившись с лангобардами, разгромили после нескольких войн в 567 г. своих врагов гепидов, союзников императора. Гепиды тщетно просили императора о военной помощи, однако войско прислано не было. Возможно, это был роковой просчет во внешней политике империи. Императору достались только несколько знатных беглецов гепидов с королевской казной и пограничный город Сирмий. Авары обосновались на землях гепидов в Среднем Подунавье и вскоре вторглись в пределы империи, требуя тот же Сирмий как принадлежащий им по праву войны. В 574 г. после крупного поражения имперского войска под командованием Тиберия был заключен унизительный для императора мир с аварами. Лангобарды же с массой примкнувших к ним союзников весной 568 г. беспрепятственно захватили Северную и Центральную Италию. Войск для оказания им сопротивления собрано не было. Только в 573 г. в Италию было послано войско во главе с зятем Юстина Бадуарием, однако оно было разгромлено лангобардами. Одновременно оживились враги империи в Африке, где в 569–571 гг. мавры нанесли серию поражений римским войскам, и в Испании, где в 569–572 г. империя потеряла несколько крупных городов. Тем не менее престиж империи на Востоке был еще достаточно велик. В 571 г. восставшие против персов армяне попросили помощи у Юстина и перешли в подданство империи. Иберия, Албания и жившие к северу от Кавказа аланы и сабиры также приняли сторону императора. В Армению и Албанию в том же году было послано войско под командованием Феодора и Курса. Главнокомандующим же был назначен Маркиан. В 572 г. 3-тысячное войско под командованием Сергия, Феодора и дукса Халкиды Ювентина совершило набег на персидскую Арзанену. Однако сил у империи здесь было явно недостаточно, и персы снова заняли отпавшую было от них Армению. В 573 г. Маркиан одержал блестящую победу у Нисибина, но не смог развить успех, т. к. был смещен императором. В ответ войско взбунтовалось и тут же было разбито персами. Персы разграбили сельские области Сирии и заняли после долгой осады главную пограничную крепость империи в этом регионе — Дару.