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