В римскую армию входили большие пограничные войска, которые защищали границы империи, и полки преторианской гвардии, стоящие в Риме. Но к IV веку армия устарела и перестала быть эффективной, а преторианская гвардия не раз показывала свою неверность правительству. Поэтому Константин решил организовать новую армию, которую, однако, построил по старым римским принципам. Но даже несмотря на то, что ему и его преемникам удалось построить новые вооруженные силы с сильной маневренной кавалерией, поддерживаемой многочисленной пехотой, они продолжали считать императорских телохранителей, схолов, подобно римской преторианской гвардии более раннего периода, ядром армии.

Научили императора маневренному ведению войны заклятые враги византийцев — персы. До того как арабы набрали силу в VII веке, Сасанидская Персия была самым мощным военным государством своего времени, однако в прошедшем тысячелетии персам неоднократно приходилось вступать в серьезные схватки с беспокойными кочевниками Центральной Азии. Эти необузданные и бесстрашные наездники открыли персам много новых способов ведения войны, подвергая их стремительным атакам маневренной кавалерии. Персы взяли их опыт на вооружение и поспешили ввести в свою армию конные отряды, которые с большим успехом использовали в борьбе против римлян. Византийцы также усвоили урок, и, хотя пехота оставалась их главной силой в Европе, они довольно быстро поняли, что кавалерия незаменима в войнах на Востоке, где конные лучники лучше всех справляются с персами. Сначала кавалеристы получали ту же плату, что и пехотинцы. Но через несколько десятков лет «катафракты», то есть тяжелая кавалерия, стали получать более щедрое вознаграждение, чем любой другой род войск, включая легкую кавалерию, «трапезитов». С VI столетия безопасность Малой Азии в большей степени обеспечивали конные лучники. Общая численность кавалерии, «кабаллария фемата», составляла приблизительно 120 тысяч человек.

Императоры Тиберий II (578–582) и Маврикий (582–602) сочли необходимым реорганизовать армию. Оба не изменили ее полной зависимости от монарха. Она должна была состоять из первоклассных полков, похожих на гвардейские, их называли «палатины», и полков похуже, их называли «комитатенсы». Тиберий решил разделить армию на три части в соответствии с тремя основными регионами страны: Восток, Иллирия и Фракия. В каждую входило от шести до восьми полков по 3–4 тысячи человек. Каждой армией командовал дукс, или магистр милитум, а полком — стратег (генерал или трибун), хотя этот титул также давали губернаторам провинций.

Стратег кавалерии стоял выше стратега пехоты. В отличие от гражданского правителя района дукс получал контроль над территорией, включающей в себя несколько районов или провинций. Он отвечал за все войска в своем регионе, но военными операциями на деле руководили стратеги. Каждый генерал должен был собирать и содержать собственный полк, обеспечивая людей луками и мечами. За это полку присваивалось его имя. Ни один из них не превышал по численности 7 тысяч человек; число военнослужащих постоянно менялось, и эффективность их была низка. Дукс, командиры и генералы подчинялись напрямую императору. Как и других офицеров, императоры назначали их и платили им, но им давалось право самостоятельно набирать неофицерский состав.

Несмотря на то что Маврикия убили его же солдаты во время похода на балканских славян, он тем не менее много сделал для повышения эффективности и благополучия армии. Благодаря его стараниям в 590 году появился первый в Византии военный устав. В соответствии с мыслями, изложенными в этой работе, Маврикий провел несколько реформ. Самой важной из них было введение обязательной военной службы для мужчин, не достигших сорока лет. Также он отдал три полка, во главе каждого из которых стоял генерал, под начало общего главнокомандующего. Каждый из полков должен был состоять из трех бригад, которые, в свою очередь, делились на семь отрядов по 400 человек. Помимо того, Маврикий попытался создать соединения запаса из лучников, в которых призывники служили по тем же принципам, что в британской территориальной армии. В мирное время им надлежало упражняться в стрельбе из лука всего раз в неделю.

Практически с самого начала нехватка людей затрудняла воплощение идей императора. Полки невозможно было укомплектовать из-за недостаточного количества регулярных солдат, и властям приходилось полагаться преимущественно на наемников. Никому не отказывали в зачислении в армию по национальному признаку, принимали даже гуннов и лангобардов, однако большинство наемников происходили из Германии и Иллирии. Всем им хорошо платили, и многие из них, начиная еще с IV века, сумели дорасти до высших чинов.

В VII веке нехватка людей в армии ощущалась настолько сильно, что император Ираклий разработал оригинальную схему привлечения новобранцев. Этот процесс известен как фемная реформа. Он начался в восточных пограничных районах. Эти территории при всей своей уязвимости были крайне плохо защищены, поскольку не пользовались любовью армии. Чтобы сделать назначение в эти области более желанным, Ираклий пообещал каждому солдату, служащему в соединениях «Анатоликон» (то есть анатолийском), «Армениакон» (армянском) и «Опсикон», земельный надел, который перейдет в его собственность и который он сможет возделывать и получать с него доход. Солдат мог жениться и жить на этом участке в качестве своего рода военного землевладельца, но взамен должен был являться по приказу на защиту границ от захватчиков вооруженным и на коне. Специально отобранным людям поручалось выполнять обязанности паспортиста и часового, который проверяет документы у странников и конного караула, заступая в наряд на башни, стоящие на расстоянии 900–1200 метров, но в пределах видимости друг для друга, чтобы они могли подать сигнал соседнему посту наблюдения. Хозяин фемы имел право завещать свой надел старшему сыну при условии, что тот пойдет по стопам отца и станет военным. Младшим сыновьям была уготована судьба свободных крестьян, но им надлежало самостоятельно заботиться о себе и приобретать невозделанную землю в малонаселенных приграничных районах. Предполагалось, что таким образом они увеличат крестьянское население отдаленных территорий и количество сельхозпродукции, получаемой на землях империи. Потомственные хозяева фем могли нанимать слуг и иметь рабов, которые помогали им с тяжелой работой.

Изобретение системы фем привело к четкому разделению армии. Пограничные войска отделились от войск, стоящих в столице. Последние состояли из полков пехоты и наступательных соединений, которыми командовали доместики, вместе с четырьмя самыми важными полками формируя схолы. Каждым из полков командовал друнгарий, а не доместик. Схолой в целом руководил офицер, который часто являлся и главнокомандующим всей армии. Но с конца X века один доместик ставился во главе восточной армии или схолы, а другой — во главе западной. С другой стороны, Ираклий возложил каждую фему на стратига, который выступал в роли и военного командира местных соединений, и губернатора района. Таким образом, Ираклий вывел фемы из управления преторианских префектов, но не позволил стратигам собирать налоги с сельских жителей. Вместо этого он возложил эту обязанность на офицеров-сборщиков, которые были назначены в фемах. Стратиги получали более высокую зарплату, чем гражданские чиновники, управлявшие районами раньше.