Положение спасли наемники, в том числе из варварской Европы. Они появились в Ромейском царстве уже с начала X в. Через столетие, в начале XI в. государство стало предоставлять всем желающим стратиотам, отягченным военной службой, право откупаться от нее. Но так как своих «профессионалов войны» не хватало, на эти средства набиралось все больше наемников. Среди них было большое количество воинственных народностей, населяющих Империю, — армян, македонцев, фессалийцев, но основную массу составляли иноземцы — норманны, росы, болгары, армяне, грузины, англо-саксы (инглины), франки, датчане (даны), немитцы (немцы), италы (италийцы), далматинцы, сарацины (арабы), хазары, пачинакиты (печенеги), аланы, авасги — подлинный «интернационал», этакий «Французский легион». Из них формировались особые полки-тагмы. Постепенно фемное войско превращалось во вспомогательные части при профессиональном наемном, хорошо оплачиваемом из казны: плата наемникам в полтора-два раза превосходила плату византийского стратиота. Кроме того, наемник получал ежемесячные выплаты
Примечательно, что в составе византийских войск вновь появляется подзабытая должность
В результате происшедших изменений к последней четверти XI в. ромейская армия сократилась до 20–25 тысяч воинов. Она стала в десять раз малочисленней, но зато качественно более мощной, стойкой, и, что очень важно, политически благонадежной. Ваилевсы отбирали в нее лучших специалистов, среди которых особенно ценились норманнские тяжеловооруженные конники, конные печенеги, конные арабские или пешие армянские лучники. Когда наемникам, будь это греки или чужеземцы, регулярно платили, они воевали с не меньшей отвагой, чем стратиоты, и главное, более профессионально, а значит, эффективно. Служебное рвение подогревалось и узаконенной перспективой подтверждаемого «Прохироном» раздела захваченной добычи.
Византийский военно-морской флот состоял из длинных весельных судов-дромонов (дромониев) — «гонщиков», или, как их стали называть с IX в., —