Особенно быстро росло число наемников в XI в. Это были и крещеные арабы, и армяне, и грузины, и печенеги, и половцы, и аланы, и пришельцы с Запада. С 70-х годов XI в. появились среди них и турки. Наемники-иноземцы прибывали в империю и поодиночке, и группами в несколько сот человек, как, например, русские и варяги. Армяне и грузины приходили иногда на зов василевса воинскими соединениями и играли крупную роль в военных действиях в Малой Азии. Изредка империя нанимала целую армию у правителей иных стран. Но это было и дорого и опасно. Болгарское войско, позванное василевсом для подавления восстания Фомы Славянина, получив плату, на обратном пути грабило местное население. Войско Святослава, приглашенное Никифором II для ведения совместной войны с болгарами, всерьез стало угрожать самой Византии.
Анна Комнин считала, что закованные в броню западные рыцари непобедимы. Глядя на сражающегося Никифора Катакалона, пишет она, его можно было принять "за уроженца Нормандии, а не ромея" — так он был могуч и искусен. Мануил I, по словам Никиты Хониата, знал, что воины-ромеи подобны "глиняным горшкам", а западные наемники — "металлическим котлам". Исаак II, несмотря на нищету отечественных воинов, отдавал захваченных на войне коней не им, а наемникам с Запада, так как они лучше действовали тяжелым копьем — вооружением конника. Обидеть иноземных наемников было гораздо опаснее, чем стратиотов-ромеев. Василевсам не раз приходилось подавлять их грозные бунты, а затем идти на серьезные уступки.
Особые отряды воинов, находившихся на службе у магната, которые появились уже в Х в., ни тогда, ни впоследствии не превратились в настоящее войско, с которым феодалы могли бы, как на Западе, участвовать в походе государя-сюзерена. Магнат шел в битву с небольшим собственным отрядом оруженосцев, полувассалов, слуг и родственников. Такие отряды не играли серьезной роли в сражениях. Вассалитет не стал в империи развитой и всеобщей системой.
Не избавила империю от необходимости содержать большое наемное войско и система так называемых проний, которая стала развиваться во второй половине XII в. Пронии — пожалования императора в пользу частных лиц, заключающиеся в передаче им права управлять определенной территорией с государственными и свободными крестьянами и собирать с них налоги в свою пользу.
Помимо сухопутных сил, империя имела также военный флот: провинциальный, используемый в основном для сторожевой службы, и центральный — царский, игравший главную роль в крупных экспедициях. Кроме того, на побережье Малой Азии и на островах находилось несколько морских фем, население которых содержало сильный военный флот и несло преимущественно морскую службу в качестве гребцов и военных моряков.
