Однако ведение успешных наступательных войн имело и оборотную сторону. Возрастающие требования новых средств на оплату армии вызывали растущее противодействие знати, не желавшей платить налоги, и в первой половине XI в. в империи возросла социальная напряженность, что нашло отражение и в образовании при дворе политических группировок. Правительство Византии переоценивало собственную военную мощь и пренебрегало организацией обороны, поскольку было слишком озабочено противодействием сепаратизму провинциальной знати. Это ослабляло обороноспособность империи. Прежние военные округа пришли в упадок, а наемники начали играть на противоречиях в государстве, принимая то одну, то другую сторону; в результате возникали междоусобицы, подточившие мощь империи. Кончилось это тем, что центральная Анатолия стала добычей кочевников-турок.

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

Термин «фема», прежде означавший военный округ, еще использовался, но означал просто провинцию. Теперь существовала новая система военных округов, сложившаяся в X–XI вв. К концу царствования Мануила I (1143–1180) их сеть покрывала всю Малую Азию от Трапезунда на юго-восточном побережье Черного моря на запад через Пафлагонию и западную оконечность центрального плато до Киликии. Командующие этими региональными округами именовались «дуками» («герцогами») и, как правило, располагали не только военной, но и гражданской властью, которая распространялась в той или иной степени на всю соименную провинцию, в которой они находились, в то время как коменданты крепостей и городских гарнизонов подчинялись особым начальникам, прокате-менам (prokathemenoi), которым помогали или содействовали кастрофилаксы (castrophylax), ответственные за оборону крепостей.

Тем не менее сооружение новых крепостей, содержание их гарнизонов вместе с отмобилизованной армией обходилось слишком дорого и в конечном счете оказалось чересчур тяжелым бременем для имперской казны и ресурсов. Все слабости, присущие административной системе Комнинов, постепенно выявились после ухода из жизни в 1180 г. Мануила I. Вторжение сицилийских норманнов на Балканы и Четвертый крестовый поход положили конец надеждам на возрождение власти империи в Малой Азии. Однако созданные при Комнинах оборонительные структуры очень пригодились правителям Никейской империи, образовавшейся в западной части Малой Азии после захвата крестоносцами Константинополя в 1204 г. Используя эти структуры, они смогли сдерживать натиск турок в Малой Азии. Но содержание системы военных округов с регулярными частями, находящимися под командованием дук, требовало больших расходов, которые императоры из династии Палеологов могли позволить себе лишь непродолжительное время. Поэтому приходилось во многих случаях полагаться на иноземных наемников, хотя правительство Палеологов не отказалось и от использования собственных военных сил. Никейские императоры охотно нанимали солдат и офицеров из числа католиков, особенно кавалеристов, хотя скоро возникли значительные различия в оплате между рядовыми наемниками и отдельными «латинскими» рыцарями, которые получали право попечительства или пронойи. К концу XIII в. основное различие между полевыми армиями и провинциальными гарнизонами состояло в том, что первые комплектовались в основном наемниками или содержались за счет попечительства (пронойи), а вторые содержались в основном за счет фискальных льгот. Но в то же время наблюдается и постепенное снижение числа наемников из Европы, причем «латинян» вытесняют турки, впоследствии игравшие более заметную роль, причем многие из таких наемников относятся к числу tourkopouloi, «туркопулов», как именовали крещеных турок.

По мере истощения ресурсов все большее и большее количество солдат полевых армий переходят на содержание с помощью пронойи, причем медленно тает различие между полевой армией и гарнизонами. С конца XIII в. в источниках упоминаются несколько разных категорий военнослужащих, которые служили в возрожденном военном флоте Византии при Михаиле VIII и различались по происхождению и виду службы: гасмулами (gasmouloi) обычно именовались наемники греко-латинского происхождения; цаконы или лаконцы (tzakones, lakones), выходцы из южного Пелопоннеса, служили наемниками в легковооруженных войсках. Телематоры (thelematarioi, добровольцы) служили за земельные пожалования, предоставлявшиеся императорами возле Константинополя; просаленты (prosalentes) служили за пожалования землей на островах или в определенных приморских районах гребцами на кораблях имперского флота. Те и другие, очевидно, имели наследственный статус. После сокращения флота в 1285 г. (после перемирия с Венецией) различия между этими группами постепенно стираются: В XIV в., по мере утраты Византией земель Анатолии, гарнизоны европейских провинций содержатся в основном за счет земельных пожалований и фискальных льгот, и на такую же основу переходит содержание полевых армий, в которых существуют также и вспомогательные наемные части, создаваемые для особых целей из числа как иностранцев, так и подданных империи. Были повышены налоги на содержание наемников, в том числе с попечительств.

С начала XIV столетия военачальники провинций, возглавлявшие их администрацию, стали именоваться кефала-ми (головами; от греч. kephale). Районы, которыми они руководили, назывались катепаникиями (katepanikia) и, как правило, включали в себя крепость с прилегающими к ней территориями. Прежние дуки и прокатемены со своими округами исчезают по мере того, как территория империи сжимается до минимума. Фискальное управление оставалось по-прежнему самостоятельным и прямо контролировалось центром.

Имперская армия XIV–XV вв. представляла собой пеструю картину. В ее состав входили союзники-федераты из соседних стран — сербы, болгары, аланы (с Северного Кавказа), куманы (половцы), а также крестьянские провинциальные ополчения, служившие на основе освобождения от налогов, иностранцы, получавшие землю за военную службу (таким образом, например, в начале XIV столетия привлекали на военную службу куманов), иностранные наемные отряды, например, составленные из каталонцев, а также те, кому были пожалованы права пронойи. Начиная с 1320— 1330-х гг. в европейских войнах империя пользовалась услугами турецких наемников и союзных ей эмиров из Малой Азии. К 1330-м гг. большая часть Малой Азии (кроме нескольких приморских городов) уже была потеряна империей, и ей приходилось проводить в этом регионе политику лавирования и компромиссов. Обычно такие части служили в течение определенной кампании, после чего возвращались по домам. К концу XIV в. в имперской армии преобладают турецкие «союзники», тогда как сербы и болгары практически перестают в ней служить, прежде всего в связи с началом захвата Балкан турецкими войсками.