Научили императора маневренному ведению войны заклятые враги византийцев — персы. До того как арабы набрали силу в VII веке, Сасанидская Персия была самым мощным военным государством своего времени, однако в прошедшем тысячелетии персам неоднократно приходилось вступать в серьезные схватки с беспокойными кочевниками Центральной Азии. Эти необузданные и бесстрашные наездники открыли персам много новых способов ведения войны, подвергая их стремительным атакам маневренной кавалерии. Персы взяли их опыт на вооружение и поспешили ввести в свою армию конные отряды, которые с большим успехом использовали в борьбе против римлян. Византийцы также усвоили урок, и, хотя пехота оставалась их главной силой в Европе, они довольно быстро поняли, что кавалерия незаменима в войнах на Востоке, где конные лучники лучше всех справляются с персами. Сначала кавалеристы получали ту же плату, что и пехотинцы. Но через несколько десятков лет «катафракты», то есть тяжелая кавалерия, стали получать более щедрое вознаграждение, чем любой другой род войск, включая легкую кавалерию, «трапезитов». С VI столетия безопасность Малой Азии в большей степени обеспечивали конные лучники. Общая численность кавалерии, «кабаллария фемата», составляла приблизительно 120 тысяч человек.
Императоры Тиберий II (578–582) и Маврикий (582–602) сочли необходимым реорганизовать армию. Оба не изменили ее полной зависимости от монарха. Она должна была состоять из первоклассных полков, похожих на гвардейские, их называли «палатины», и полков похуже, их называли «комитатенсы». Тиберий решил разделить армию на три части в соответствии с тремя основными регионами страны: Восток, Иллирия и Фракия. В каждую входило от шести до восьми полков по 3–4 тысячи человек. Каждой армией командовал дукс, или магистр милитум, а полком — стратег (генерал или трибун), хотя этот титул также давали губернаторам провинций.
Стратег кавалерии стоял выше стратега пехоты. В отличие от гражданского правителя района дукс получал контроль над территорией, включающей в себя несколько районов или провинций. Он отвечал за все войска в своем регионе, но военными операциями на деле руководили стратеги. Каждый генерал должен был собирать и содержать собственный полк, обеспечивая людей луками и мечами. За это полку присваивалось его имя. Ни один из них не превышал по численности 7 тысяч человек; число военнослужащих постоянно менялось, и эффективность их была низка. Дукс, командиры и генералы подчинялись напрямую императору. Как и других офицеров, императоры назначали их и платили им, но им давалось право самостоятельно набирать неофицерский состав.
Несмотря на то что Маврикия убили его же солдаты во время похода на балканских славян, он тем не менее много сделал для повышения эффективности и благополучия армии. Благодаря его стараниям в 590 году появился первый в Византии военный устав. В соответствии с мыслями, изложенными в этой работе, Маврикий провел несколько реформ. Самой важной из них было введение обязательной военной службы для мужчин, не достигших сорока лет. Также он отдал три полка, во главе каждого из которых стоял генерал, под начало общего главнокомандующего. Каждый из полков должен был состоять из трех бригад, которые, в свою очередь, делились на семь отрядов по 400 человек. Помимо того, Маврикий попытался создать соединения запаса из лучников, в которых призывники служили по тем же принципам, что в британской территориальной армии. В мирное время им надлежало упражняться в стрельбе из лука всего раз в неделю.
Практически с самого начала нехватка людей затрудняла воплощение идей императора. Полки невозможно было укомплектовать из-за недостаточного количества регулярных солдат, и властям приходилось полагаться преимущественно на наемников. Никому не отказывали в зачислении в армию по национальному признаку, принимали даже гуннов и лангобардов, однако большинство наемников происходили из Германии и Иллирии. Всем им хорошо платили, и многие из них, начиная еще с IV века, сумели дорасти до высших чинов.