Наступательный характер войн середины IX в. оказал значительное влияние на военную организацию империи.
Ополчение провинций не могло более эффективно выполнять новые задачи, и потому стали формироваться полевые армии с более сложной тактической структурой, более совершенным вооружением, имеющие специальные боевые навыки и боевой дух; руководящую роль в этих войсках постепенно приобрела военно-землевладельческая знать провинций. Полностью профессиональные военные части играют все большую роль по мере того, как государство переводит оплату военным в денежную форму и на эти деньги берет на службу наемников. В результате появляется пестрая интернациональная армия, в которой наряду с местными профессионалами, как в пехоте, так и в кавалерии служат русы, норманны, турки, франки и т. д. Быть может, наибольшую известность приобрела варяжская гвардия — варанги, впервые сформированная при Василии II и состоявшая из скандинавских наемников, искателей приключений. Среди их командиров самым знаменитым был Гаральд Гардрад, позднее, в 1046–1066 гг., ставший королем Норвегии и принявший смерть от руки английского короля Гаральда Годвинссона в 1066 г. в битве при Стамфордском мосту. Гаральд Гардрад воевал в составе варяжских частей в 1034–1041 гг.
Падение значения прежних, возглавлявшихся стратегами фемных армий стало результатом возникновения новых тактических и стратегических командных структур. Создаются новые военные регионы, подчиненные новым независимым командирам, началом которых послужило преобразование небольших пограничных частей — клисур — в фемы, в которые включались также завоеванные регионы, однако новые округа были небольшими и группировались вокруг центральных укреплений. По мере дальнейшего развития этой системы на границах были размещены более крупные и эффективные в военном отношении подразделения имперских тагм (tagmata). На границе стали служить особые профессиональные части, подобные гвардейским. Начиная с 970-х гг. эти части объединяются в более крупные воинские соединения, во главе каждого из которых ставится дукс (дука; от doux) или катепан (katepano), независимый от местного военного округа-фемы. Новые пограничные округа превратились в буферные провинции, защищавшие прежние фемы и тактически не зависевшие друг от друга с точки зрения доступного военного персонала. Подобная система создается на востоке, на Балканах и на западе империи. Полевые армии, на границах и в провинциях, все в большей мере состояли из наемников-профессионалов или из войск, присланных вассальными правителями, соседями империи.
Однако ведение успешных наступательных войн имело и оборотную сторону. Возрастающие требования новых средств на оплату армии вызывали растущее противодействие знати, не желавшей платить налоги, и в первой половине XI в. в империи возросла социальная напряженность, что нашло отражение и в образовании при дворе политических группировок. Правительство Византии переоценивало собственную военную мощь и пренебрегало организацией обороны, поскольку было слишком озабочено противодействием сепаратизму провинциальной знати. Это ослабляло обороноспособность империи. Прежние военные округа пришли в упадок, а наемники начали играть на противоречиях в государстве, принимая то одну, то другую сторону; в результате возникали междоусобицы, подточившие мощь империи. Кончилось это тем, что центральная Анатолия стала добычей кочевников-турок.
В правление династии Комнинов после 1081 г. были проведены серьезные военные и фискальные реформы, позволившие относительно стабилизировать внутреннее и в известной мере международное положение Византии. Хотя иностранные наемники еще продолжали играть большую роль, создание разных родов войск, в которых служили только византийцы, позволило империи сражаться с внешними врагами, не завися от иноземных войск. В основе этих перемен лежало как улучшение налоговой системы, так и передача налогов на откуп отдельным лицам, которые, в свою очередь, обязывались поставлять для армии обученных воинов, конных и пеших. Заимствование с запада новых видов оружия, таких как арбалет, и тактики тяжелой кавалерии были отличительными чертами этого периода.
Термин «фема», прежде означавший военный округ, еще использовался, но означал просто провинцию. Теперь существовала новая система военных округов, сложившаяся в X–XI вв. К концу царствования Мануила I (1143–1180) их сеть покрывала всю Малую Азию от Трапезунда на юго-восточном побережье Черного моря на запад через Пафлагонию и западную оконечность центрального плато до Киликии. Командующие этими региональными округами именовались «дуками» («герцогами») и, как правило, располагали не только военной, но и гражданской властью, которая распространялась в той или иной степени на всю соименную провинцию, в которой они находились, в то время как коменданты крепостей и городских гарнизонов подчинялись особым начальникам, прокате-менам (prokathemenoi), которым помогали или содействовали кастрофилаксы (castrophylax), ответственные за оборону крепостей.
Тем не менее сооружение новых крепостей, содержание их гарнизонов вместе с отмобилизованной армией обходилось слишком дорого и в конечном счете оказалось чересчур тяжелым бременем для имперской казны и ресурсов. Все слабости, присущие административной системе Комнинов, постепенно выявились после ухода из жизни в 1180 г. Мануила I. Вторжение сицилийских норманнов на Балканы и Четвертый крестовый поход положили конец надеждам на возрождение власти империи в Малой Азии. Однако созданные при Комнинах оборонительные структуры очень пригодились правителям Никейской империи, образовавшейся в западной части Малой Азии после захвата крестоносцами Константинополя в 1204 г. Используя эти структуры, они смогли сдерживать натиск турок в Малой Азии. Но содержание системы военных округов с регулярными частями, находящимися под командованием дук, требовало больших расходов, которые императоры из династии Палеологов могли позволить себе лишь непродолжительное время. Поэтому приходилось во многих случаях полагаться на иноземных наемников, хотя правительство Палеологов не отказалось и от использования собственных военных сил. Никейские императоры охотно нанимали солдат и офицеров из числа католиков, особенно кавалеристов, хотя скоро возникли значительные различия в оплате между рядовыми наемниками и отдельными «латинскими» рыцарями, которые получали право попечительства или пронойи. К концу XIII в. основное различие между полевыми армиями и провинциальными гарнизонами состояло в том, что первые комплектовались в основном наемниками или содержались за счет попечительства (пронойи), а вторые содержались в основном за счет фискальных льгот. Но в то же время наблюдается и постепенное снижение числа наемников из Европы, причем «латинян» вытесняют турки, впоследствии игравшие более заметную роль, причем многие из таких наемников относятся к числу tourkopouloi, «туркопулов», как именовали крещеных турок.
По мере истощения ресурсов все большее и большее количество солдат полевых армий переходят на содержание с помощью пронойи, причем медленно тает различие между полевой армией и гарнизонами. С конца XIII в. в источниках упоминаются несколько разных категорий военнослужащих, которые служили в возрожденном военном флоте Византии при Михаиле VIII и различались по происхождению и виду службы: гасмулами (gasmouloi) обычно именовались наемники греко-латинского происхождения; цаконы или лаконцы (tzakones, lakones), выходцы из южного Пелопоннеса, служили наемниками в легковооруженных войсках. Телематоры (thelematarioi, добровольцы) служили за земельные пожалования, предоставлявшиеся императорами возле Константинополя; просаленты (prosalentes) служили за пожалования землей на островах или в определенных приморских районах гребцами на кораблях имперского флота. Те и другие, очевидно, имели наследственный статус. После сокращения флота в 1285 г. (после перемирия с Венецией) различия между этими группами постепенно стираются: В XIV в., по мере утраты Византией земель Анатолии, гарнизоны европейских провинций содержатся в основном за счет земельных пожалований и фискальных льгот, и на такую же основу переходит содержание полевых армий, в которых существуют также и вспомогательные наемные части, создаваемые для особых целей из числа как иностранцев, так и подданных империи. Были повышены налоги на содержание наемников, в том числе с попечительств.