Едва он вернулся в столицу, как сразу же официально отрекся от своих прежних клятв верности Риму. Патриарх Иоанн Векк, главный поборник церковного единства, был лишен престола. Иосифа, прежнего патриарха, находившегося уже в совершенно дряхлом состоянии, внесли в главный собор на носилках и торжественно интронизировали во второй раз. Но он не протянул долго, и после продолжительного междуцарствия Андронику удалось обеспечить избрание афонского монаха Афанасия, жившего ранее отшельником. Набожному императору аскетизм нового патриарха казался очень уместным – это отвлекало внимание церкви от политических вопросов. А в глазах клириков Афанасий был всего лишь немытым фанатиком во власянице, озабоченным только одним – преследованием священнослужителей за их мирские устремления и накопленные богатства. Летом 1293 г. делегация ведущих иерархов церкви потребовала его смещения, и в октябре Афанасий сложил с себя обязанности, но перед этим он официально подверг анафеме своих врагов.
В следующем году вдовствующий император взял в жены одиннадцатилетнюю Иоланту, дочь Вильгельма V, маркиза Монферратского. Вильгельм до этого именовал себя королем Фессалоник, но теперь уступал титул Андронику: не должно оставаться более никаких двусмысленностей в отношении статуса второго города в империи. Но Андроник знал, что, если на Фессалоники будет совершено нападение, он не сможет прийти на помощь: василевс уже сократил до минимума свои вооруженные силы.
Поскольку почти ежедневно происходило уменьшение азиатских владений империи, представляется почти невероятным, что Андроник мог действовать подобным образом. Византия давно уже опиралась на силу наемнических войск; Андроник сократил их численность до самоубийственного уровня – расформировав при этом закаленные полки и отдав предпочтение отрядам, состоявшим из бродяг и беженцев. Дешевизна подобного войска никак не могла компенсировать отсутствие дисциплины и опыта. Андроник в придачу упразднил и военно-морской флот – к вящей радости генуэзцев, которые могли требовать теперь значительно большую плату за свою поддержку. Между тем турки, достигнув Средиземноморья, начали строить собственный флот, и они с охотой прибегали к квалифицированному наставничеству тысяч неимущих византийских моряков, которые теперь оказались вынуждены обращаться к мусульманам за работой.
Турки-сельджуки уже более не представляли собой ту единую боевую силу, какую они являли во времена своего расцвета. Разгром армии султана монголами в 1243 г. фактически положил конец его власти в Анатолии. Однако несколько турецких племен, стремительно отступавших под натиском монголов, в итоге обосновались на ничейной земле вдоль византийской границы, откуда начали осуществлять регулярные набеги на имперскую территорию. Вскоре они нашли оправдание этим рейдам, определив их как форму исламского джихада – священной войны против неверных. Их следующим естественным шагом было определение себя как гази – воинов веры. К началу XIV столетия лишь несколько крупных византийских крепостей – Никея и Никомедия, Сарды и Бруса, Филадельфия и Магнесия – и считанное число изолированных портов, таких как Ания на Эгейском побережье и Гераклея на побережье Черного моря, еще продолжали держаться; за этими исключениями вся Анатолия оказалась поглощена турками.
На Западе ситуация также ухудшалась стремительными темпами. Константинополь ликовал, когда Карл Анжуйский умер в 1285 г., оставив трон своему сыну Карлу II, но вскоре оказалось, что молодой король настроен не более дружелюбно к Византии, чем его отец. В 1291 г. – когда состоялось падение Акры, последнего крестоносного государства Отремера, – Карл предложил Никифору Эпирскому сцементировать их союз браком между сыном короля Филиппом и дочерью деспота Тамарой. Так, Филипп стал повелителем всех греческих владений Карла, получив титул принца Тарентского, и обрисовалась вторая анжуйская угроза Константинополю.
Между тем в Сербии в 1282 г. наследовал престол новый король Стефан Милутин, взявший имя Стефан Урош II. Он заявил о поддержке анжуйцев, заключил союз с Эпиром, объявил войну империи и сделал своей столицей Скопль, стратегический опорный пункт, позволявший контролировать дорогу, идущую на Фессалоники. Стефан также скрепил союз с Иоанном Дукой Фессалийским, женившись на его дочери. Сербско-фессалийский альянс угрожал не только Фессалоникам – под прицелом оказалась вся дорога, ведущая через Балканский полуостров к Адриатике.
В 1297 г. измученный войнами с Сербией Андроник, узнав, что жена Милутина умерла, решился на дипломатический ход: предложил сербскому королю свою дочь от Иоланты Симониду. Правда, девочке исполнилось только пять годков, а ее предполагаемый муж приближался к сорокалетию, но эту жертву следовало принести. На Пасху 1299 г. Андроник лично сопровождал Симониду в Фессалоники, где ее ждал жених.