Армия Восточной Римской империи в VI в. состояла из двух основных контингентов: стационарных пограничных войск, известных под названием лимитанеи (limitanei), которые состояли в основном из старых легионов, и вспомогательных отрядов и мобильных полевых сил, комитатов (comitatenses), состоявших в основном из частей, созданных в конце III–IV вв. Существовали также гвардейские части, сосредоточенные вокруг столицы и императорского дворца и называвшиеся палатинской гвардией (palatini). Конечно, такое деление было до известной степени условным, так как часть мобильных войск на постоянной основе стояли в городах в качестве гарнизонов. Мобильные части делились на несколько армий во главе с региональными командующими, или магистрами милитум. В 600 г. н. э. было девять таких армий, две из которых базировались в районе Константинополя. Подразделения флота, предназначенные для ведения военных действий на море и реках, входившие в структуру, созданную еще Юстинианом и носившую название квестура эксцерцитус (quaestura excercitus), базировались в главных портах Балкан и Сирии, в то время как сухопутные силы и флот на Дунае обеспечивались и снабжались из Эгейского региона по морю.

Солдат рекрутировали частично на добровольной основе, частично — на основе военного призыва, для которого использовались списки работников, подлежавших обложению налогом capitatio-iugatio, хотя для формирования мобильных частей начиная с VI в. основным стал добровольный принцип. Мобильные полевые армии дополнялись местными войсками, куда, помимо пограничников-лимитанеев, входили подразделения, располагавшиеся в провинциях, чреватых внутренними смутами (например, таких, в которых был распространен разбой). Эти части также находились под началом региональных командующих. На 560 г. насчитывалось 25 таких частей, в основном в приграничных районах.

Такой двухуровневый порядок родился после кризиса III столетия, и он более или менее отвечал задачам обороны империи вплоть до окончания войны 602–626 гг. с персидским Сасанидским царством. Однако он не смог противостоять исламскому завоеванию, вызвавшему потерю восточных провинций вместе со всеми их ресурсами в 634–642 гг. Правительство отреагировало на это отводом в период после 637–640 гг. мобильных войск в глубь страны, прежде всего в западную и центральную Малую Азию. Там эти войска расквартировывали в различных районах, так что провинции, занятые той или иной армией, получали наименование по этой армии. Группы провинций постепенно превратились в военные округа, или фемы (themata), полевые армии — в войска типа ополчения, и в каждом таком войске существовало ядро профессиональных командиров, чья служба оплачивалась за счет центра или провинций. Во главе фем стояли военачальники — стратиги, которым к концу IX в. были подчинены также фискальные чиновники этих округов. Впоследствии фемы получили чисто географические названия. Гражданская администрация, первоначально частично подчиненная военной, постепенно реформировалась, и обе власти были приведены в равновесие. Различия между полевыми и пограничными войсками постепенно исчезли.

После 640 года возникли также серьезные проблемы со снабжением и содержанием войск. Еще до арабского завоевания восточных земель в империи не хватало наличных денег на жалованье армии, а позднее эта ситуация ухудшилась. Налоги в районах, где стояли войска, взимались преимущественно в натуральной форме, чтобы можно было скорее содержать войска, чем платить военным жалованье. Этот процесс и привел к превращению армий в своего рода ополчения, причем местные округа соперничали с другими фемами в борьбе за императорскую милость. Кроме того, вероятно, с конца VII в. восстанавливается наследственный институт для отдельных категорий рекрутов. Наряду с этим от профессиональных военных, владевших землей, в ряде случаев стали требовать, чтобы они сами обеспечивали себя частью оружия и необходимого снаряжения, для чего им предоставлялись определенные налоговые льготы. В результате к X столетию сложилась привилегированная категория военного землевладения, которую государство рассматривало как основу комплектования провинциальных армий. Начиная примерно с конца VIII в. и далее вооруженные силы империи комплектовались из нескольких различных категорий новобранцев: профессиональных военнослужащих, составлявших ядро войск в фемах, ополченцев, составлявших основную массу этих войск, имперских гвардейских частей в столичном регионе и иностранных наемников (хазар, курдов, турок и др.). В тот же период произошла и реорганизация военного флота Византии. Было создано несколько региональных флотилий для защиты побережий, поскольку с середины VII в. арабские военные корабли превратились в серьезную угрозу империи.

Армии снабжались из различных источников. Начиная с IV по VII в., все войсковые подразделения обеспечивались продовольствием. С конца V в. на востоке на пропитание выделялись денежные средства, на которые полковые уполномоченные покупали непосредственно у производителей или на рынке провиант и все необходимое для солдат, а потом распределяли между ними. Мобильные подразделения получали необходимую часть из доходов провинций, расплачиваясь за них расписками для учета в налогообложении на будущий год. Администрация префектов следила за тем, чтобы военные поставки были учтены при налогообложении. О прохождении через регион воинских частей местные власти извещались заранее, чтобы они имели возможность разместить припасы вдоль маршрута следования войска.

Все необходимое — одежду, вооружение, коней — армия получала посредством натуральных поставок, а также из государственных мастерских. В городах империи работали несколько оружейных заводов. С конца VI в. оружие и одежду для армии можно было также купить из специально выделенных для этого государственных средств. Коней армия получала благодаря натуральным налогам, а кроме того, их покупали у владельцев по твердым ценам; часть лошадей поставляли с имперских конных заводов. Железная руда, уголь и дрова поступали в армию также благодаря натуральным налогам.

После кризиса, вызванного исламским завоеванием во второй половине VII в., в этой системе произошли значительные изменения. Основная тяжесть расходов по содержанию армии была переложена на плечи местного населения. Денежные выплаты военным были существенно урезаны и была создана система натуральных налогов на содержание войск непосредственно с местного населения. Благодаря натуральным налогам войска получали оружие, одежду, лошадей и вьючных животных. Для этого войска были широко распределены по регионам, в результате чего возросла зависимость армии от личных солдатских хозяйств как в области провианта, так и вооружения. В конце VIII столетия многих провинциальных солдат призывали в армию только на сезон. При этом оружие, верховые и вьючные животные поставлялись по натуральному налогу. Однако, несмотря на все изменения в системе снабжения армии, в этот период оставалось много общего с той, какой она являлась до 650-х гг., и к IX столетию она, хотя в урезанном и деформированном виде, сохранила прежнюю, позднеримскую основу.

Возникшие в VII–VIII столетиях структуры носят обобщенное название «системы фем». Восстановление относительной политической и экономической стабильности в империи, а также раздоры среди ее врагов позволили Византии к 800 г. добиться некоторой стабильности. Несмотря на несколько серьезных поражений, империя в целом проводит более активную, наступательную политику и на востоке, и на севере, сочетая, как например против болгар, военные действия с миссионерской и дипломатической деятельностью. Несмотря на ожесточенное сопротивление мусульманских эмиров в первой половине X в., Византия смогла успешно отвоевать у них многие земли в северной Сирии и Ираке, разгромить Второе Болгарское царство и начать повторное завоевание Сицилии и южной Италии. Ко времени кончины императора Василия II (1025), Византийская империя снова превратилась в могущественную державу Средиземноморья, соперничать с которой мог только Фатимидский халифат в Египте и Сирии.