Την περίοδο από το 1025-1081, η αυτοκρατορία αντιμετώπισε τα μεγαλύτερα προβλήματα στα ανατολικά σύνορά της. Τον 11ο αιώνα εμφανίστηκαν οι Ογούζοι, τουρκική φυλή, που έμειναν γνωστοί ως Σελτζούκοι από το όνομα του γενάρχη τους Σελτζούκ. Ήταν νομάδες κτηνοτρόφοι που βρίσκονταν στα ανατολικά της Κασπίας όπου και εξισλαμίστηκαν. Το 1055 ο ηγέτης των Σελτζούκων κυρίευσε τη Βαγδάτη και πήρε από το χαλίφη τον τίτλο του Σουλτάνου. Aπό το 1045/6 οι Βυζαντινοί άρχισαν να αντιμετωπίζουν τις επιδρομές τους. Οι Τούρκοι ήταν καλοί πολεμιστές και εκμεταλλευόμενοι το γεγονός της εξασθένισης της άμυνας του Βυζαντίου σημείωσαν πολλές επιτυχίες. Οι επιδρομές εντάθηκαν με το σουλτάνο Αλπ Αρσλάν (1063-1072) και κατέληξαν στη μάχη του Μαντζικέρτ το 1071, που σήμανε την αρχή της ίδρυσης του ισχυρού κράτους των Σελτζούκων.

Το βυζαντινό κράτος αντιμετώπισε όμως πολλούς εχθρούς και επαναστάσεις και στα βόρεια σύνορά του. Η οριστική κατάκτηση της Βουλγαρίας έφερε το Βυζάντιο αντιμέτωπο με τους Ούζους, τους Κουμάνους και τους Πετσενέγκους. Οι Πετσενέγκοι, συχνά με την υποστήριξη και την ενίσχυση των Ούζων, άρχισαν να περνούν το Δούναβη και να αποτελούν κίνδυνο για τα βυζαντινά σύνορα. Συχνά μάλιστα λεηλάτησαν περιοχές ακόμη και στο ελληνικό έδαφος. Ωστόσο, το βυζαντινό κράτος την περίοδο αυτή κατόρθωσε να διατηρήσει τα σύνορα του στον ποταμό Δούναβη, αντιμετωπίζοντας τα προβλήματα πότε με στρατιωτικά μέσα και πότε με τη διπλωματία, ακόμη και με αυτοκρατορικά δώρα.

Αλλά και στην Κάτω Ιταλία και τη Σικελία η κατάσταση χειροτέρευσε. Oι Nορμανδοί, έχοντας ιδρύσει νέο βασίλειο στην Ιταλία, γίνονταν όλο και πιο επικίνδυνοι και η συμμαχία Ιταλών-Βυζαντινών δεν κατόρθωσε να αναχαιτίσει τη δύναμή τους εξαιτίας του Σχίσματος το 1054. Το 1060 οι Νορμανδοί κατέλαβαν το μεγαλύτερο μέρος της νότιας Ιταλίας και περνώντας στη Σικελία κατάφεραν μέσα σε μια δεκαετία, μέχρι το 1072, όχι μόνο να την κατακτήσουν ολόκληρη αλλά να έχουν βλέψεις και για την Κωνσταντινούπολη.