Хазарская империя начала сокращаться в размерах с конца IX в., теснимая различными степными народами, которых привела в движение экспансия печенегов и их союзников. Венгры (мадьяры), жившие к западу и северо-западу от Хазарии, с середины IX в. на территории нынешней Венгрии, к началу X в. создали свое государство, разгромив местные славянские княжества. Хазары, как и мадьяры, служили в византийских войсках наемниками, особенно в войнах против болгар, однако укрепившееся к концу X в. и принявшее христианство Венгерское королевство постепенно превратилось в потенциальную угрозу Византии на Среднем Дунае. Хазары продолжали играть важную политическую роль в Степи до середины X в., когда Киевская Русь, мощь которой к этому времени возросла, разгромила хазарское государство и сменила Хазарию в системе византийской дипломатии. Появление в конце IX в. печенегов (пацинаков) нарушило сложившуюся биполярную схему. Пришельцы воевали и с хазарами, и с мадьярами, заняв в степи регион между Доном и Дунаем. Их ценность для Византии, как противовеса и Руси, и мадьярам, была очевидной, особенно в войнах конца X в., но все же печенеги были опасными и ненадежными союзниками. В середине XI в. печенеги начали перемещаться на Балканы, где столкнулись с имперскими войсками. До начала гражданских войн и поражения при Манзикерте в 1071 г. их удавалось в какой-то мере сдерживать, но потом они стали грабить и опустошать пограничные регионы, почти не встречая сопротивления, и только в 1091 г. Алексей I смог разгромить их.
X столетие ознаменовалось для Византийской империи огромными достижениями как в культурном развитии, так и в смысле возвращения большинства бывших римских территорий на Востоке. Эти успехи начались благодаря победам талантливых полководцев при Льве VI (886–912) и Константине VII (912–959) и продолжались в правление «солдатских императоров» Никифора I Фоки (963–969) и Иоанна I Цимисхия (969–976). В эту эпоху в состав империи вошли значительные территории северной Сирии, были разгромлены войска эмиров на западе Междуречья, вновь отвоеваны Крит и Кипр, завоеван район Антиохии и едва не был снова присоединен Иерусалим. Хотя правление Василия II (976—1025) началось гражданской войной и поражением на Балканах, но и при нем продолжалось в целом восстановление и консолидация Византийской империи, и после продолжительной и тяжелой войны ему удалось разгромить Болгарское царство. Земли болгар были включены в состав империи и разделены на провинции, находившиеся под их собственным управлением. Дунай снова превратился в северную границу империи, а на Востоке эмират Алеппо и соседние с ним эмираты стали данниками Византии. Там ее соперником стал Египет, управляемый династией Фатимидов, которая также пыталась осуществлять экспансию в Сирии.