После потери Сирии и Палестины, которые перешли арабам в VII веке, была реорганизована вся система обороны империи. Именно тогда получила широкое распространение идея создания оседлых территориальных войск вдоль границ Малой Азии. Нормальной административной единицей был отряд примерно в 350 человек. Число таких отрядов в данном соединении колебалось и никогда не было постоянным, так что неприятелю невозможно было оценить силу, противостоящую ему. Впрочем, военные силы Византии никогда не были особенно большими. Велизарий покорил Африку с 15 тысячами солдат, а в Х веке вся византийская армия насчитывала 140 тысяч человек.
В ранний период служба в армии была обязательной, а ветеранов награждали земельными пожалованиями (грантами) в Малой Азии. Завоевание этой территории в XI столетии сельджуками ослабило оборонительную систему империи самым серьезным образом. После этого вместо службы принимались налоги, что подрывало и размеры армии, и ее боевой дух, потому что воинской службы можно было избежать, и личности, по сути своей ненадежные, за плату заменяли настоящих рекрутов. Мануил I Комнин ухудшил положение еще больше, когда присоединил к общей казне налоговые сборы, предназначенные на содержание армии. С тех пор византийцам пришлось полагаться только на войско, состоящее из наемников, которые в целом были гораздо менее надежны, хоть и лучше обучены, вроде знаменитой варяжской гвардии.
Хотя задачи, стоявшие перед армией, не уменьшались и оставались неизменными на протяжении всей византийской истории, флот играл такую же жизненно важную роль. Византийцы одни владычествовали на море вплоть до 700 года, когда их господство стали оспаривать мусульмане. Матросами на мусульманском флоте того периода были в основном сирийцы, многие из которых были христианами, но придерживались монофизитской ереси, а потому с готовностью служили мусульманским хозяевам. По сути дела, благодаря их умению и выучке был осажден Константинополь в 670 году.
Но хотя мусульмане обосновались в Южном Средиземноморье, византийцы не потеряли своих позиций на севере. Византийский флот сумел спасти Константинополь во время арабского набега в 718 году. Черное море всегда считалось греческой вотчиной. С переносом халифата из Дамаска в Месопотамию и утверждением династии Аббасидов роль Сирии уменьшилась, вследствие чего византийский флот ослабел без прежней поддержки и внимания. Результаты этого оказались фатальными: когда в 825 году мусульмане захватили Крит, это не только отдало в их руки важный стратегический центр, но и предоставило отличную базу мусульманским пиратам, которые потом долгие годы составляли серьезную угрозу торговому судоходству в этом районе. В IX веке византийский флот был все же реорганизован. В 961 году был возвращен Крит, и с того момента ситуация продолжала улучшаться. Последовавшее расширение Византии на Запад произошло в немалой степени благодаря мощи ее флота. Сильный военный флот обеспечивал безопасность торговому судоходству и тем самым способствовал его росту. К середине XI столетия византийские купцы захватили под свой контроль торговлю не только в Северном, но и Восточном и Южном Средиземноморье. В 1047 году Наст-и-Хосров отмечал, что Сирия страшилась византийских атак с моря. Константин VII мог справедливо похвастаться тем, что ему подвластно все Средиземное море вплоть до Гибралтара. Но в ходе XI столетия финансовая нестабильность центрального правительства империи привела к тому, что византийские морские силы стали сдавать свои позиции латинянам, сначала амальфийцам, потом венецианцам и генуэзцам.