Ранние военные предприятия Василия были по большей части неудачны (что отчасти объясняется аристократическим заговором против молодого императора). В 986 г. он отправился в поход против Болгарии, возродившейся под властью царя Самуила. После смерти Цимисхия он вместе со своими братьями восстал против ромейского владычества в Македонии и утвердил свою столицу сначала в Преспе, а потом в Охриде. В соответствии со старинной болгарской традицией, Македония стала политическим центром новой империи. Оттуда Самуил стремился расширить свое влияние на северные и восточные области, и к середине 980-х гг. он уже правил всеми историческими землями Болгарского государства до самого Дуная и западных Балкан, включая большую часть Фессалии, Эпира и территорию современной Албании. Он даже начал выдавливать византийцев из Фракии, нападая в 985 и 986 гг. на Салоники и другие главные центры провинции.
Юный Василий должен был принять срочные меры прежде, чем весь полуостров будет навсегда потерян для ромеев. Экспедиция во главе с императором двинулась на север, в район Сердики, но оказалась не в состоянии взять город. Ромейские войска были изрядно потрепаны в горных проходах, даже багаж императора оказался по ходу дела утерянным. Разразившиеся вскоре гражданские войны на несколько лет отвлекли внимание Василия от Балкан, позволив Самуилу значительно укрепить и расширить свое государство. Когда император снова обратил свой взор на запад, он столкнулся там с очень серьезными проблемами.
В 991 г. Василий решился наконец бросить вызов болгарскому царю, находившемуся в то время в зените своего могущества. Император начал с попытки сколотить дипломатические союзы с некоторыми из балканских правителей вроде князей Сербии. Кампания 991 г. в Македонии была краткой и успешной, но восточная политика снова всецело завладела Василием до 1001 г. Тем временем, в 997 г. Самуил понес тяжелое поражение от одного из византийских полководцев, Никифора Ураноса, преследовавшего его до самого Пелопоннеса. Но эта частная удача не могла повлиять на общую ситуацию стратегического равновесия. Начиная с 1001 г., Василий проводит ряд ежегодных кампаний и благодаря вышколенным и отлично экипированным войскам последовательно наносит противнику ряд тяжелых ударов. Действия Василия были хорошо продуманы. Сначала он вбил клин от византийской Фракии до Балканских гор и Плиски, отрезав таким образом основные владения Самуила в Македонии от самого сердца Болгарии. Тактикой двойных охватов он успешно теснил воинство царя примерно до 1007 г., пока военные действия не свелись к обнаружению главных сил Самуила и принуждения их к сражению. Развязка наступила в 1014 г., когда, в ходе сражения в Клейдонском ущелье, которое царь укрепил на случай византийского нападения, его армия была окружена и полностью уничтожена. Самуил умер вскоре после сражения, возможно, от кровоизлияния в мозг или острого сердечного приступа, и четыре года спустя остатки его империи распались в результате гражданской войны. Впервые с VI в. весь балканский регион до самого Дуная был снова в руках ромеев и оставался под властью империи до конца XII столетия.
Мастерство и способности ромейских военачальников этого периода иллюстрируются множеством сражений. Одно из самых известных — на реке Сперхион в 997 г. Царь Самуил вторгся тогда во Фракию, где успешно заманил в западню и захватил Ашота — сына византийского командующего в Салониках, Григория Таронита. В тщетной попытке спасти сына Григорий тоже попал в засаду и погиб, пытаясь вырваться из окружения.
Самуил пересек северную Грецию, спустился до Коринфского залива и вторгся в Пелопоннес, предавая все на своем пути огню и мечу. По дороге на юг ему удалось избежать столкновений с имперскими войсками, но на обратном пути он был принужден к сражению одним из самых способных полководцев империи, Никифором Ураносом, близким другом императора Василия и создателем выдающегося для своего времени военного руководства. Никифор, назначенный на пост главнокомандующего всех западных армий, выступил из Салоников и перешел через Олимп. Выйдя к Ларисе, он оставил там большую часть обоза. Оттуда он отправился налегке на перехват Самуила. Пройдя форсированными маршами всю Фессалию и Фарсальскую равнину и с ходу форсировав реку Апиданос, достиг Сперхиона, где его разведчики обнаружили болгарский лагерь. Никифор разбил свой лагерь напротив Самуила, но это нисколько не смутило царя: брода поблизости не было, а река из-за проливных дождей широко разлилась.
Никифор и не думал отступать перед трудностями. Послав разведку в обе стороны вдоль реки, он все-таки обнаружил подходящее место для переправы. Под покровом ночной темноты ромеи покинули лагерь. Благополучно форсировав реку, они двинулись прямо на болгар. Еще до рассвета византийская армия стояла в полной боевой готовности против слабо укрепленного и плохо охраняемого лагеря неприятеля, где никто не ожидал нападения. Прозвучала команда, и воины ринулись вперед. Болгары были захвачены спящими, и ни о каком организованном сопротивлении не могло быть и речи. Те, кто уцелели от ромейских мечей, по большей части попали в плен. Сам Самуил и его сын Роман, оба тяжело раненные, спрятались под грудой мертвых тел и лежали тихо, пока не смогли незамеченными выбраться и скрыться. Победителям достался весь царский обоз со всей захваченной добычей. Они вернулись в Салоники, ведя за собою большое количество пленников.
Упрямый отказ пасовать перед препятствиями, которые всем казались непреодолимыми, демонстрировали лично Василий II и его полководцы в кампании 1014 г. В предыдущие годы ромейская стратегия ограничения возможностей неприятеля до такой степени ослабила сопротивление Самуила, что вместо планов масштабного наступления он занимался только отражением постоянных византийских рейдов на свою территорию и сохранением того, что можно было уберечь. Стратегия царя состояла в попытках предотвращения ежегодных разрушительных набегов в самое сердце своих македонских владений.
В тот год военные действия, как всегда, начались в мае. От Серры на юге, через горный проход Рупел имперские войска по длинной равнине реки Стримона устремились вглубь страны. Следуя старинной болгарской тактике, Самуил преградил проходы деревянными палисадами и рвами, особенно укрепив важное Клейдонское ущелье, которое имперские армии регулярно занимали на пути в Македонию. В то же время был организован диверсионный рейд против Салоник, который закончился разгромом болгарских войск армией Феофилакта Вотаниата. Однако попытка запереть Клейдонское ущелье привела к полной катастрофе. Натолкнувшись там на высокий палисад, установленный болгарами, ромеи сначала пробовали штурмовать его в лоб, но потеряли много людей и уже решили обойти препятствие с запада или с востока, однако фактически это было бы равносильно откладыванию кампании на будущий год. Один из полководцев Василия, Никита Ксифас, командующий войсками Филиппопольского района, предложил провести небольшой отряд по горам в обход неприятеля. Главные силы тем временем, чтобы усыпить бдительность болгар, продолжали демонстрации перед проходом. Разведчикам Ксифаса удалось найти труднопроходимую узкую тропу к западу от ущелья, и на рассвете 29 июля обходная колонна с громовыми боевыми криками, многократно усиленными эхом, как снег на голову свалилась на тылы оборонявшихся. Воспользовавшись возникшим замешательством и отсутствием организованной защиты, ромеи решительным штурмом с фронта овладели палисадом и немедленно обрушили его. Началось страшное побоище, много болгарских воинов было зарублено, но еще больше окруженных было вынуждено сдаться в плен.
