Тем временем на свободе оставался сильный союзник Вриенния – стратиг из Пафлагонии по имени Никифор Василаки[46]
. Василаки был дукой Диррахия при Михаиле Парапинаке и получил от василевса приказ арестовать Вриенния, однако его не выполнил и присоединился к мятежнику. В 1078 году Василаки захватил Фессалонику и после разгрома Вриенния провозгласил себя императором. Армия Алексея Комнина выступила против Василаки осенью 1078 года. В битве на реке Вардар недалеко от Фессалоники Алексей прибегнул к хитрости. Разбив лагерь на берегу Вардара таким образом, что только русло реки отделяло его от армии Василаки, Алексей ночью вывел свои войска из лагеря, оставив дымящиеся полевые кухни, костры, палатки и обоз, полный денег. Василаки устремился в лагерь, думая, что Комнин, потеряв бдительность, отдыхает от долгого марша, и нашел там лишь монаха Иоанникия, которого приставила к Алексею его мать Анна Далассина в качестве денщика. Раздосадованный Василаки бегал по лагерю и кричал: «Куда девался картавый?» [ποῦ ποτέ ἐστιν ὁ τραυλός;], смеясь над дефектом речи Комнина, а воины Василаки бросились грабить лагерь. Этого только и ждал Алексей. Едва солдаты Василаки рассеялись по лагерю, Комнин атаковал со всех сторон. Сам Алексей напал на кого-то из высших архонтов армии Василаки, облаченного в богатые доспехи. Как пишет Анна, «в его латах отражалось сияние звезд» [καὶ γὰρ ἀντέστιλβε τούτῳ τὰ ὅπλα πρὸς τὴν ἀστρῴαν βολήν]. Алексей подумал, что перед ним сам узурпатор, однако ошибся. Он сразил архонта, и солдаты Василаки окончательно потеряли способность оказывать организованное сопротивление.В гуще боя один из франкских рыцарей чуть не убил Комнина, но Алексей крепко сидел в седле, вовремя окликнул рыцаря по имени и пригрозил ему. Брат Никифора Василаки Мануил пытался воодушевить солдат на продолжение борьбы, но был выбит из седла ударом булавы воином по имени Василий Куртикий и доставлен связанный Алексею Комнину. Никифор Василаки бежал в Фессалонику, где забаррикадировался в местном акрополе, но был выдан горожанами Алексею и, позднее, ослеплен слугами Никифора Вотаниата.
Маневр Комнина, примененный в битве на реке Вардар, будет впоследствии с успехом повторен Алексеем в битве под Касторией, где василевс сможет окружить и разбить крупные силы норманнов под командованием Боэмунда Тарентского. Победы Алексея Комнина над «тиранами» – именно так назывались неудачливые мятежники согласно византийской политической терминологии – сделали молодого стратига крайне популярным в столице. Он снискал благоволение молодой красавицы – императрицы Марии Аланской и получил от императора Никифора Вотаниата чин великого доместика схол. Однако в этот момент Византия оказалась в смертельной опасности. Опасность эта исходила с Запада, из южной Италии, где безраздельно господствовал Роберт Гвискар, норманнский герцог Апулии и Калабрии, захвативший весной 1071 года город Бари, последний оплот Византийской империи на Апеннинском полуострове.