Возможно, Иоанн Дука преследовал неприятеля и перенес боевые действия на территорию его владений. Однако Алексей понимал, что его армия не может увязнуть в Сербии в то время, когда турки Чаки угрожают Константинополю. Боевые действия завершились уже осенью 1091 года заключением договора, который уточнял границу между Византией и Дуклей. Бодин дал обещание прекратить набеги на византийские фемы.
Уже через три года после разгрома печенегов при Левунионе, примерно в 1094 году, в приднепровских степях объявился проходимец, который разъезжал по половецким таборам и объявлял себя Константином – порфирородным сыном законного государя императора Романа Диогена, преданного и ослепленного изменниками Дуками в 1072 году. Поскольку император Алексей был женат на представительнице рода Дук – императрице Ирине, тень соучастия в свержении Романа Диогена падала и на него. Алексей был объявлен узурпатором. В действительности, Константин Диоген погиб в бою под Антиохией еще в 1073 году, задолго до прихода к власти Алексея. Лже-Диоген был охотно принят в кибитках хана Тугоркана, бывшего еще совсем недавно союзником Алексея Комнина в борьбе против печенегов. То ли Тугоркана настолько потрясла жестокая расправа ромеев над пленными печенежскими семьями при Левунионе (что, впрочем, маловероятно, учитывая образ жизни и характер войн, которые вели сами половцы)? То ли Тугоркан, побывавший на территориях балканских фем империи в кампанию 1091 года, убедился в ее слабости и уверовал в возможность завоевания Константинополя подобно Чаке? То ли Тугоркан прослышал о Лже-Михаиле – самозванце, выдававшем себя за свергнутого Михаила VII Парапинака, которого использовал Роберт Гвискар в начале своего похода на Византию в 1081 году? В результате, хан решил оказать Лже-Диогену помощь, снабдив его половецкой дружиной, во главе которой сам же и находился. Половцы вторглись в северные фемы Византийской империи через Зиг, получив помощь от местных валахов. Такие крепости как Голоя и Диамболь открывали ворота самозванцу, облаченному в порфиру и пурпурные императорские сапоги. Стратиг Голои был выдан Лже-Диогену и закован в кандалы. По пути половцы грабили те немногочисленные деревни и города, которые еще не были опустошены печенегами. Новое вторжение кочевников, таившее серьезную политическую опасность, заставило Алексея действовать чрезвычайно энергично. Он сосредоточил лучшие войска и преградил путь противнику в районе Анхиала, в результате чего половцы повернули на Адрианополь. Самозванец уверял, что стратиг Адрианополя Никифор Вриенний, в свое время совершивший вместе с покойным императором Романом Диогеном чин братотворения, окажет помощь его сыну. Никифор отверг предложения Лже-Диогена и выдержал осаду города половцами в течении 48-ми суток. Затем половцы были отброшены от города ромеями, а самозванец ранен.
Однако наступление половцев на Адрианополь вновь создало угрозу Константинополю, а несчастная фема Македония, полностью разоренная в течении предшествующих войн с печенегами, из-за новых боевых действий не могла вернуться к нормальной хозяйственной жизни. Поэтому император Алексей решил прибегнуть к хитрости, о которой подробно рассказывает Анна. К Лже-Диогену подослали лазутчика по имени Алакасей, который в свое время хорошо знал Романа Диогена. Одетый в рубище лазутчик просил сообщить самозванцу, что бежал от «узурпатора» Алексея, дабы поступить на службу законному государю вместе с комендантом крепости Пуца. По словам Алакасея, комендант готов сдать крепость Лже-Диогену и ждет его прибытия. Ни о чем не подозревавший Лже-Диоген отправился в Пуцу вместе с Алакасеем и небольшим половецким отрядом. В крепости устроили праздник и пир, а когда половецкие воины изрядно напились и уснули, то были без труда перебиты неожиданно нагрянувшими ромеями. Лже-Диоген был арестован и ослеплен сельджуком по имени Камир по приказу Анны Далассины, матери императора. Его отправили в Константинополь в сопровождении Камира и евнуха Евстафия Киминиана. Тем временем, войска Алексея атаковали главные силы половцев, которые рассыпались по окрестностям в поисках в богатых деревнях фуража для коней и ценностей. Ромеи без труда уничтожали отдельные группы кочевников, многие из которых занимались грабежом и не были готовы к битве. Хан Тугоркан потерпел жестокое поражение и был вынужден бежать со своей дружиной за Дунай. Эта победа императора Алексея на некоторое время обезопасила дунайскую границу империи и дала возможность навести порядок в разоренных войной балканских фемах.