Войны с Болгарией Василию приходилось неоднократно прерывать ради походов на Восток. Главным врагом империи здесь в это время стали Фатимиды — египетские халифы, постоянно посягавшие на Сирию и враждовавшие не только с Византией, но и с Хамданидами — эмирами Алеппо, союзниками и данниками империи. Эмиры Алеппо трепетали перед египетской угрозой и постоянно просили помощи у Василия, но готовы были при случае порвать зависимость от Византии. Василию приходилось зорко следить за союзниками и нередко обуздывать их вооруженной рукой, однако союз с ними был необходим. Обычно крайне бережливый, император в борьбе за Северную Сирию не жалел денег, подкупая местное духовенство и арабских эмиров.
После подавления мятежа Склира, эмир Алеппо отказался выплачивать дань, обусловленную договором 969 г. В 981 г. Варда Фока, осадивший по приказу императора Алеппо, вынудил эмира согласиться на выплату ежегодно 400 тыс. дирхемов, но в 983 г. Фоке пришлось повторить поход, чтобы заставить эмира уплатить дань за два года. В 985 г. население Алеппо снова отказалось платить дань. Произошли серьезные столкновения. Однако вскоре обманувшийсяв надежде на помощь Египта алеппский эмир возобновил договор с Византией. Укрепление союза с Алеппо и обострение отношений с Фатимидами произошло в начале 90-х годов. В конце 991 г. умер эмир Алеппо Сейф-ад-Даула. Фатимиды решили захватить Алеппо. Эмир Дамаска по приказу египетского халифа осадил Алеппо, разбил летом 992 г. войска сына Сейф-ад-Даулы, разорил византийские владения вокруг Антиохии. Выступивший на помощь Алеппо дука Антиохии Михаил Вурца и его армянское союзное войско были разгромлены. Весной 995 г. в ответ на отчаянные призывы эмира Алеппо Василий появился под стенами Алеппо. Эмир Дамаска поспешно ушел от города. Василий вторгся во владения Фатимидов, взял Рафанею и Эмесу, повергнув в ужас арабов своей жестокостью. Но занять Триполи ему не удалось. Дукой Антиохии стал Дамиан Далассин.
Ответом Фатимидов на поход Василия было новое нападение эмира Дамаска, длившееся три года. Рафанея и Эмеса были отвоеваны, окрестности Антиохии и Алеппо опустошены. Дамиан Далассин потерпел жестокое поражение и погиб в сражении. В 999 г. Василий должен был совершить новый поход в Сирию. Был взят Шейзар; Рафанея и Эмеса сожжены и разрушены. Осада Триполи была безуспешной и на этот раз. Отвлекаемый неожиданно обострившейся обстановкой в Иверии и Армении и войной с болгарами, Василий вступил в переговоры с халифом и в первой половине 1001 г. заключил с Фатимидами десятилетнееперемирие35
. Но это перемирие фактически кончилось уже через три года. Среди арабских племен и соседних эмиров в 1004—1005 гг. распространяется идея священной войны за веру. Новый египетский халиф ал-Хаким проводил открыто враждебную империи политику. В 1015—1016 гг. Алеппо, наконец, попал во власть Фатимидов. Василию удалось завязать дружбу с египетскими наместниками Алеппо, тяготившимися зависимостью от Каира. Положение на границах с арабами было восстановлено.Значительно расширил Василий владения империи и на северо-востоке Малой Азии, в Армении и Иверии. В 990 г. он совершил поход на Кавказ против правителя Иверии Давида и Багратидов, оказавших помощь Варде Фоке. Соединенные войска Багратидов и Давида были разбиты. Давид признал зависимость от Византии и завещал подвластные ему земли императору. В 1001 г. Давид умер. Некоторые из иверийских князей не захотели признавать завещания Давида, и Василий поспешил на Кавказ. Князья области Тайк должны были подчиниться, архонт внутренней Иверии обязался не посягать на уступленные Давидом земли36
.Однако укрепить позиции империи в Иверии и Армении Василию удалось лишь в конце царствования. В походах 1021—1024 гг. Василий II нанес несколько поражений правителю Абхазии Георгию, пресек его попытки заключить военный союз с ал-Хакимом и мятежной военной знатью Георгий был вынужден признать зависимость от империи и отдал императору своего сына Баграта в заложники. Во время этих походов правитель Васпуракана передал Василию все свои земли. Сын умершего в 1020 г. Гагика I, царя Ани, Смбат заключил с Василием договор, подобный тому, который ранее заключал с императором Давид37
. В результате этих приобретений на северо-востоке империи появились новые фемы Васпуракан, Иверия и Феодосиополь.