Από τον 11ο αιώνα και μετά, οι ένοπλες δυνάμεις του Βυζαντίου εισήλθαν σε μια περίοδο μετάλλαξης. Οι αυτοκράτορες άρχισαν να φροντίζουν περισσότερο τα λεγόμενα «Τάγματα», δηλαδή τις επίλεκτες επαγγελματικές μονάδες, και παραμέλησαν εντελώς τους τοπικούς «Θεματικούς Στρατούς», που αποτελούνταν από τους κατοίκους της κάθε περιοχής. Παράλληλα, η απώλεια των μικρασιατικών εδαφών στέρησε από την Κωνσταντινούπολη την μεγαλύτερη δεξαμενή ανθρώπινου δυναμικού που διέθετε. Αυτοί και άλλοι παράγοντες, σε συνδυασμό με τις γενικότερες κοινωνικές και οικονομικές συνθήκες μιας σταδιακής παρακμής, είχαν ως αποτέλεσμα την εκτεταμένη χρήση ξένων μισθοφόρων από τους Βυζαντινούς. Την ίδια πρακτική ακολούθησαν και τα ελληνικά κράτη που προέκυψαν μετά την άλωση της Κωνσταντινούπολης από τους Σταυροφόρους, το 1204, όπως η Αυτοκρατορία της Νίκαιας ή το Δεσποτάτο της Ηπείρου. Οι μισθοφόροι των Βυζαντινών προέρχονταν κυριολεκτικά από όλα σχεδόν τα έθνη του τότε γνωστού κόσμου.
Ούγγροι. Στρατιώτες ουγγρικής καταγωγής πρωτοεμφανίστηκαν στην υπηρεσία των Βυζαντινών αυτοκρατόρων τον 12ο αιώνα. Το 1137 αποτέλεσαν τμήμα των δυνάμεων του Ιωάννη Β΄ Κομνηνού, στην εκστρατεία του εναντίον των Σελτζούκων. Αργότερα, κατά τον 13ο αιώνα, Ούγγροι πολεμιστές συμμετείχαν στον στρατό της Αυτοκρατορίας της Νίκαιας, σε διάφορες επιχειρήσεις μικρής ή μεγάλης κλίμακας. Η πιο σημαντική από αυτές ήταν αναμφισβήτητα η μάχη της Πελαγονίας, το 1259. Στην αποφασιστική εκείνη σύγκρουση, η Αυτοκρατορία της Νίκαιας συνέτριψε τους Λατίνους της Ελλάδας και τους Ηπειρώτες συμμάχους τους, θέτοντας τα θεμέλια για την ανακατάληψη της Κωνσταντινούπολης από τους Φράγκους. Οι Ούγγροι του βυζαντινού στρατού συγκροτούσαν πάντα βοηθητικά τμήματα ιππικού.
Λατίνοι. Οι μισθοφόροι των Βυζαντινών που αναφέρονται στις πηγές ως Λατίνοι ή Φράγκοι, ήταν στην συντριπτική τους πλειοψηφία Γάλλοι, ενώ σε πολύ μικρότερους αριθμούς, Ιταλοί, Ισπανοί και Γερμανοί. Υπηρετούσαν κυρίως ως ιππότες, δηλαδή βαριά θωρακισμένοι ιππείς, και σπανιότερα ως πεζοί. Οι τελευταίοι χρησιμοποιούσαν συνήθως βαλλίστρες ενώ από τα 1400 και μετά χειρίζονταν και φορητά πυροβόλα. Οι πρώτοι Λατίνοι στην υπηρεσία της Κωνσταντινούπολης εμφανίστηκαν τον 11ο αιώνα και ήταν Νορμανδοί της Ιταλίας και της Σικελίας. Αργότερα, βασικές πηγές Φράγκων μισθοφόρων για τους βυζαντινούς στρατούς, αποτέλεσαν τα σταυροφορικά κρατίδια τα οποία ιδρύθηκαν στην Παλαιστίνη και την Ελλάδα. Η Αυτοκρατορία της Νίκαιας έκανε ίσως την πιο εκτεταμένη χρήση Λατίνων στρατιωτών, που αποτελούσαν την βασική δύναμη κρούσης του στρατού της. Το Δεσποτάτο της Ηπείρου διέθετε το 1230 αρκετούς Ιταλούς, ενώ χρησιμοποίησε 400 επίλεκτους Γερμανούς ιππότες στην μάχη της Πελαγονίας. Οι Λατίνοι μαζί με τους Τούρκους έφθασαν να αποτελούν τα πιο πολυπληθή σώματα ξένων μισθοφόρων στο Βυζάντιο, τα οποία χρησιμοποιήθηκαν κατά κόρον στους εμφυλίους πολέμους του 14ου αιώνα.
Τούρκοι (Σελτζούκοι, Οθωμανοί, Ούζοι, Πατζινάκες). Η Βυζαντινή Αυτοκρατορία χρησιμοποιούσε ανέκαθεν μεγάλους αριθμούς Τούρκων μισθοφόρων, αλλά από το δεύτερο μισό του 13ου αιώνα, η πρακτική αυτή κορυφώθηκε. Το 1262, ο Μιχαήλ Η΄ Παλαιολόγος είχε στην υπηρεσία του 5.000 Σελτζούκους, οι οποίοι συγκροτούσαν το λεγόμενο «Περσικόν» σώμα. Το 1337, περίπου 2.000 ομοεθνείς τους συμμετείχαν στην εκστρατεία του Ανδρόνικου Γ΄ στην Αλβανία. Ο Ιωάννης ΣΤ΄ Καντακουζηνός μίσθωσε συνολικά 11.000 Σελτζούκους πολεμιστές, την περίοδο 1343-1345 και άλλους 6.000 η αυτοκράτειρα Άννα της Σαβοΐας (Παλαιολογίνα), το 1346. Οι Οθωμανοί δεν είχαν μικρότερο μερίδιο συμμετοχής στους βυζαντινούς στρατούς. Ειδικά ο Ιωάννης ΣΤ΄ φαίνεται ότι εκτιμούσε ιδιαίτερα τις υπηρεσίες τους, χρησιμοποιώντας συνολικά 16.000 από αυτούς, μεταξύ 1345 και 1348. Ήταν περιζήτητοι ως έφιπποι τοξότες κι αυτό τους έκανε αρκετά απείθαρχους στους εργοδότες τους. Το 1350, με 20.000 Οθωμανούς, ο Ιωάννης ΣΤ΄ ανακατέλαβε την Θεσσαλονίκη από το επαναστατικό κίνημα των Ζηλωτών, οι οποίοι σχεδίαζαν να παραδώσουν την πόλη στους Σέρβους. Σύντομα, ο συγκεκριμένος αυτοκράτορας θα πλήρωνε την υπερβολική εμπιστοσύνη που είχε στους μισθοφόρους του. Το 1354, οι Οθωμανοί στρατιώτες του, κατέλαβαν για λογαριασμό τους την περιοχή της Καλλίπολης, για να μην φύγουν ποτέ από εκεί. Παρόλα αυτά, οι Βυζαντινοί άρχοντες εξακολούθησαν να χρησιμοποιούν εκτεταμένα Τούρκους μισθοφόρους, κατά τους εμφυλίους πολέμους που ερήμωσαν την αυτοκρατορία, τον 14ο και 15ο αιώνα.
Άλλα τουρκικά φύλα που συμμετείχαν στους βυζαντινούς στρατούς ήταν οι Ούζοι οι Πατζινάκες και οι Κουμάνοι. Οι τελευταίοι συγκροτούσαν το λεγόμενο «Σκυθικόν» σώμα και από τον 11ο αιώνα μέχρι τα μέσα του 14ου αποτελούσαν μια από τις σημαντικότερες μισθοφορικές δυνάμεις έφιππων τοξοτών. Το 1241, περίπου 10.000 Κουμάνοι στρατιώτες εγκαταστάθηκαν στην Ανατολία και με το πέρασμα του χρόνου εξελληνίστηκαν. Οι Ούζοι και οι Πατζινάκες προσέφεραν κι αυτοί μεγάλους αριθμούς έφιππων τοξοτών στους Βυζαντινούς, αλλά από τα μέσα περίπου το 12ου αιώνα παύουν να αναφέρονται στις πηγές.
Καταλανοί. Οι Βυζαντινοί χρησιμοποίησαν καταλανικά μισθοφορικά σώματα από την δεκαετία του 1270 μέχρι και τον 15ο αιώνα. Η πιο χαρακτηριστική περίπτωση τέτοιων στρατευμάτων ήταν η λεγόμενη «Καταλανική Εταιρεία», την οποία προσέλαβε ο Ανδρόνικος Β΄ Παλαιολόγος, το 1302, για να πολεμήσει τους Τούρκους. Η δύναμη αυτή αποτελούνταν από 1.500 ιππείς, 1.000 πεζούς και 4.000 «Αλμογάβαρους», δηλαδή ισπανικό επίλεκτο ελαφρύ πεζικό. Όμως, παρόλο που ο στρατιωτικός στόχος επιτεύχθηκε, η συνεργασία των δύο πλευρών αποδείχθηκε κάθε άλλο παρά αγαστή. Η αλαζονεία του διοικητή των Καταλανών, Ροζέ ντε Φλορ και η απροθυμία του αυτοκράτορα να τον πληρώσει, οδήγησαν σε σύγκρουση τους δύο άνδρες. Η κατάσταση γρήγορα κλιμακώθηκε και βγήκε εκτός ελέγχου. Το 1305, οι Βυζαντινοί δολοφόνησαν τον Ροζέ ντε Φλορ και οι άνδρες του άρχισαν να λεηλατούν την Θράκη και την Καλλίπολη. Έπειτα, στράφηκαν νότια, κατέκτησαν το φραγκικό Δουκάτο των Αθηνών και παρέμειναν κυρίαρχοι της πόλης μέχρι το 1387.
Αλανοί. Ιρανικό έθνος του Καυκάσου, οι Αλανοί θεωρούνταν οι καλύτεροι καβαλάρηδες της Ανατολής. Από τα τέλη του 11ου αιώνα ως τις αρχές του 14ου προμήθευαν τους Βυζαντινούς με έφιππους τοξότες. Το 1301, περίπου 7.000 Αλανοί πολεμιστές εγκαταστάθηκαν στην Θράκη, για να ενισχύσουν την άμυνα της περιοχής, παίρνοντας μισθό διπλάσιο από τους γηγενείς στρατιώτες. Πέντε χρόνια αργότερα όμως, εξολοθρεύτηκαν από τους Καταλανούς μισθοφόρους του Βυζαντινού αυτοκράτορα, που όπως αναφέρθηκε, είχαν στασιάσει εναντίον του εργοδότη τους.
Βουργουνδοί. Το 1445, ο δούκας της Βουργουνδίας απέστειλε 300 πολεμιστές για να ενισχύσει στρατιωτικά το Δεσποτάτο του Μορέως εναντίον των Οθωμανών. Παράλληλα, πολλοί μεμονωμένοι Βουργουνδοί μισθοφόροι υπηρέτησαν τους Βυζαντινούς αυτοκράτορες καθ’ όλον τον 15ο αιώνα.
Σκανδιναβοί. Η Βαράγγειος Φρουρά αποτελούσε ένα επίλεκτο μισθοφορικό τμήμα του βυζαντινού στρατού, στο οποίο υπηρετούσαν άνδρες από διάφορα έθνη της βόρειας Ευρώπης. Ως αποστολή είχαν φύλαξη του αυτοκράτορα, στον οποίο ήταν αφοσιωμένοι μέχρι θανάτου. Μέχρι τις αρχές του 13ου αιώνα, η φρουρά των Βαράγγων αποτελούνταν κυρίως από Σκανδιναβούς. Για τους Βίκινγκς ήταν μεγάλη τιμή να ταξιδέψουν ως την μακρινή Κωνσταντινούπολη και να υπηρετήσουν στην προσωπική σωματοφυλακή του αυτοκράτορα, καθώς επρόκειτο για μια θητεία που εξασφάλιζε δόξα αλλά και χρήμα. Οι Βυζαντινοί μονάρχες εκτιμούσαν ιδιαίτερα τους Βορειοευρωπαίους μισθοφόρους. Στα 1195, ο Αλέξιος ο Γ΄, ζήτησε από τους βασιλείς των σκανδιναβικών χωρών την αποστολή επιπλέον 1.200 πολεμιστών, για να τους εντάξει στην φρουρά του. Κατά την άλωση της Κωνσταντινούπολης από τους Σταυροφόρους, το 1204, οι Βαράγγοι είχαν προκαλέσει πολύ μεγάλες απώλειες στους Λατίνους εισβολείς. Αυτή όμως ήταν και η τελευταία φορά που οι πηγές μνημονεύουν Σκανδιναβούς στρατιώτες στην υπηρεσία των Βυζαντινών. Οι Βορειοευρωπαίοι μισθοφόροι πολεμούσαν ως πεζικό, ενώ βασικό τους όπλο ήταν ο μεγάλος βαρύς πέλεκυς.
Άγγλοι. Σάξονες και Άγγλοι, εμφανίστηκαν για πρώτη φορά ως μισθοφόροι των Βυζαντινών κατά την δεκαετία του 1080. Από τον 12ο αιώνα και μετά, κατατάσσονταν στην Βαράγγειο Φρουρά, ως βορειοευρωπαϊκό έθνος. Με το πέρασμα των χρόνων, ο αριθμός τους στην προσωπική σωματοφυλακή του Βυζαντινού αυτοκράτορα αυξανόταν ολοένα περισσότερο. Οι Σκανδιναβοί σταδιακά παραγκωνίστηκαν και η Βαράγγειος Φρουρά μετατράπηκε τελικά σε ένα καθαρά αγγλικό στρατιωτικό σώμα. Κάτι τέτοιο φανερώνουν και τα λεγόμενα του Μιχαήλ Η΄, ο οποίος, το 1272, αναφέρθηκε στους προσωπικούς του σωματοφύλακες με τον όρο «Αγγλοβαράγγοι». Οι άνδρες αυτοί απέδειξαν την αξία τους πολλές φορές, όπως στην πρώτη πολιορκία της Κωνσταντινούπολης από τους Οθωμανούς, την περίοδο 1394-1402. Λίγα χρόνια αργότερα, το 1404, παρατηρείται και η τελευταία αναφορά για Άγγλους μισθοφόρους στον βυζαντινό στρατό. Βασικό όπλο των πολεμιστών αυτών ήταν ο μεγάλος βαρύς πέλεκυς, όπως άλλωστε και των Σκανδιναβών προκατόχων τους.
Ρώσοι. Κατά τον 12ο αιώνα, πολλοί Ρώσοι ηγεμόνες εφοδίαζαν τον βυζαντινό στρατό με πεζούς πολεμιστές, επιδιώκοντας την διατήρηση σχέσεων φιλίας και συμμαχίας με την Κωνσταντινούπολη. Οι άνδρες αυτοί κατατάσσονταν στην Βαράγγειο Φρουρά, ως ανήκοντες σε βόρειο έθνος.
Βούλγαροι. Στην μάχη της Πελαγονίας, το 1259, οι Βούλγαροι είχαν αξιόλογη δράση, ως μισθοφόροι στον στρατό της Νίκαιας. Από τότε και μέχρι το δεύτερο μισό του 14ου αιώνα, συμμετείχαν ολοένα και πιο συχνά στους βυζαντινούς στρατούς. Οι Βούλγαροι συγκροτούσαν μονάδες ελαφρού ιππικού και μάχονταν ως έφιπποι τοξότες, έχοντας συνήθως τους δικούς τους διοικητές.
Σέρβοι. Βάσει συνθηκών που είχε επιβάλει, στις αρχές του 12ου αιώνα, η Κωνσταντινούπολη στους Σέρβους, οι τελευταίοι ήταν υποχρεωμένοι να προμηθεύουν τον αυτοκράτορα με 500 ιππείς, για διάφορες επιχειρήσεις στην Ανατολία. Το 1150 ο αριθμός αυξήθηκε σε 500 άνδρες για τα βυζαντινά στρατεύματα της Ασίας, και 2.000 για αυτά της Ευρώπης. Το 1259, στην μάχη της Πελαγονίας, 1.000 περίπου Σέρβοι πολέμησαν για λογαριασμό της Νίκαιας, ενώ η παρουσία τους στον στρατό της Κωνσταντινούπολης κορυφώθηκε, τον 14ο αιώνα. Συνήθως μάχονταν ως βαρύ ιππικό, με πανοπλία και λόγχη, αλλά και ως έφιπποι τοξότες. Οι Βυζαντινοί χρησιμοποίησαν επίσης Σέρβους αιχμάλωτους για να συγκροτήσουν νέες στρατιωτικές μονάδες. Η πρακτική αυτή όμως εφαρμόστηκε μόνο κατά την δεκαετία του 1120. Η τελευταίοι Σέρβοι που υπηρέτησαν στον βυζαντινό στρατό, ήταν οι 4.000 ιππείς του αυτοκράτορα Ιωάννη Ε΄ Παλαιολόγου, το 1352.
Αλβανοί. Κατά την διάρκεια του 14ου αιώνα, εκατοντάδες Αλβανοί μισθοφόροι αποτελούσαν τμήμα των βυζαντινών δυνάμεων στην Θεσσαλία και την Πελοπόννησο. Ο αριθμός τους αυξήθηκε σε 10.000, κατά την δεκαετία του 1390. Οι Αλβανοί υπηρετούσαν κυρίως ως ιππικό, έχοντας τους δικούς τους διοικητές, και δρούσαν συνήθως ως συνοριοφύλακες.
Γεωργιανοί. Μισθοφόροι από το βασίλειο της Γεωργίας υπηρέτησαν περιστασιακά στον βυζαντινό στρατό, κυρίως τον 12ο αιώνα αλλά και στις αρχές του 13ου. Κατά την δεκαετία του 1150, αποτέλεσαν τμήμα των αυτοκρατορικών δυνάμεων, που πολεμούσαν στην Ιταλία εναντίον των Νορμανδών. Αργότερα, ο Γεώργιος Δ΄, βασιλιάς της Γεωργίας από το 1213 ως το 1223, «δώρισε» στους Βυζαντινούς έναν μεγάλο αριθμό βοηθητικών τμημάτων του στρατού του, ως ένδειξη φιλίας και καλής θέλησης. Οι Γεωργιανοί συγκροτούσαν πάντοτε τμήματα ιππικού και ήταν εξοπλισμένοι με τόξα και λόγχες.
Αρμένιοι. Βοηθητικά σώματα Αρμενίων στρατιωτών πολέμησαν για λογαριασμό των Βυζαντινών, τόσο κατά τον 12ο αιώνα όσο και τον 13ο. Οι μονάδες αυτές είχαν συσταθεί στην Κιλικία και χρησιμοποιήθηκαν περιστασιακά στην βόρεια Συρία και την Μικρά Ασία. Σημαντική ήταν η παρουσία τους στον στρατό του πρώτου αυτοκράτορα της Νικαίας, Θεοδώρου Α΄ Λάσκαρη, το 1214. Τον 12ο αιώνα, η πανοπλία των Αρμενίων στρατιωτών δεν ξεχώριζε σε εμφάνιση από την βυζαντινή. Τον 13ο όμως αιώνα, ο εξοπλισμός τους άρχισε να διαφέρει σημαντικά, δεχόμενος έντονες δυτικές επιρροές, από τα σταυροφορικά κράτη της Μέσης Ανατολής.
Μογγόλοι. Η Αυτοκρατορία της Νίκαιας χρησιμοποίησε Μογγόλους βοηθητικούς στρατιώτες στις εκστρατείες της εναντίον των Σελτζούκων, την περίοδο 1220-1240. Στα 1282, 4.000 πολεμιστές του Νογκάι Χαν, ηγεμόνα της Χρυσής Ορδής, συμμετείχαν στον στρατό του Μιχαήλ Η΄, κατά τις επιχειρήσεις του εναντίον των Λατίνων της Θεσσαλίας. Το 1308, ο Ανδρόνικος Β΄, ανακατέλαβε από τους Οθωμανούς έναν μεγάλο αριθμό πόλεων της Βιθυνίας, χρησιμοποιώντας 30.000 Μογγόλους πολεμιστές. Πολλοί από αυτούς συμμετείχαν αργότερα και στην εκστρατεία που πραγματοποίησε ο ίδιος Βυζαντινός αυτοκράτορας εναντίον των Σέρβων.