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