Для Византии смена столетий явилась временем нескончаемых бедствий, а Андроник оказался неспособен остановить ускоряющееся падение. Константинополь даже стал полем сражения между Генуей и Венецией, на котором они разрешали свои споры. В июле 1296 г. венецианская флотилия дошла до входа в Босфор и предприняла яростную атаку на генуэзскую колонию в Галате. Когда в бой вмешался имперский гарнизон, венецианцы обратили огонь на сам город и сожгли все дома в округе. В декабре генуэзцы организовали контратаку, уничтожив главные венецианские здания в Константинополе и вырезав всех венецианцев, занимавших здесь видное положение. На следующее лето появилась новая венецианская флотилия – привезла депешу Андронику от дожа. В ней император обвинялся в том, что потворствовал генуэзцам в их агрессии, объявлялся ответственным за нанесенный венецианцам урон, и от него требовалась выплата компенсации. Эскадра прошла в Золотой Рог, подожгла одну из имперских галер и с несколькими генуэзскими пленными на борту вернулась в Венецию.
В 1299 г. Венеция и Генуя заключили сепаратный мир, однако венецианцы все еще продолжали настаивать на компенсации от Византии и летом 1302 г. предприняли третий за семь лет рейд на Константинополь. Вновь венецианцы вошли в Золотой Рог и сожгли все византийские здания в округе. Затем они заняли остров Принкипо в Мраморном море, использовавшийся в то время как лагерь для анатолийских беженцев, и стали угрожать, что вырежут их, если император не выплатит должную компенсацию. Андроник сдался, согласившись также на подписание десятилетнего договора, закреплявшего за венецианцами все их былые привилегии в Константинополе.
1302 г. стал для Византии поистине ужасным. Ранней весной сын императора и соправитель Михаил IX потерпел поражение от турок вблизи Магнесии и едва сам унес ноги. Затем произошел очередной венецианский рейд на Константинополь. А всего лишь несколько недель спустя, 27 июля, в окрестностях Никомедии византийское войско встретилось с турецкой армией, вдвое большей по численности, под командованием эмира Османа Гази. Проигранное византийцами сражение оказалось не слишком кровавым, но путь Осману теперь был расчищен и он двинулся вдоль побережья Мраморного моря, пока не достиг берегов Эгейского моря. Таким оказалось первое появление на исторической сцене человека, который, начав карьеру как правитель одного из самых маленьких эмиратов в Анатолии, в итоге основал династию, давшую свое имя Османской империи.
В этом же 1302 г. Андроник Палеолог получил послание от Рожера де Флора, главы великой каталонской компании. Эта компания, по сути, являла собой отряд профессиональных испанских наемников – преимущественно из Каталонии, но также и из других мест, – рекрутированных в 1281 г. Педро Арагонским для своих североафриканской и сицилийской экспедиций. О Рожере де Флоре известно, что он был сыном Рихарда фон дер Блюма, немецкого сокольничего Фридриха II. В возрасте восьми лет Рожер взошел на борт тамплиерской галеры. Позднее он сделался весьма успешным пиратом, после чего предложил свои услуги сыну Педро Фредерику, который немедленно назначил его адмиралом. Рожер вскоре проявил себя таким же храбрым бойцом на суше, каким был на море, и быстро приобрел себе верных последователей. Так возникла каталонская компания.
К концу 1302 г. Рожер направил к Андронику двух посланников, предложив ему услуги компании на девять месяцев. Взамен Рожер требовал оплаты этих услуг по двойному тарифу, для себя лично – титула великого дуки (в то время это был пятый по значимости титул в византийской иерархии) и руки шестнадцатилетней племянницы императора Марии. Как ни странно, Андроник принял предложение, и в сентябре 1302 г. каталонская флотилия вошла в Золотой Рог. На борту находились не только 2500 бойцов – более половины из них кавалеристы, – но также (к тихому ужасу императора) их жены, любовницы и дети: общее число приезжих оказалось около 7000. Вскоре после этого состоялось венчание Рожера и Марии, а несколько дней спустя вся компания пересекла Мраморное море и высадилась вблизи Кизика, на тот момент осаждаемого турками.
И теперь наконец каталонцы смогли продемонстрировать свои ценные боевые качества. К весне 1303 г. турки отступили на всех фронтах. Но получилось так, что Андроник дал волю силам, которые он не смог затем контролировать. Каталонцы самостоятельно принимали все решения; когда им удавалось достаточно награбить, они все оставляли себе. Властное высокомерие каталонцев вызывало постоянное недовольство у их союзников. И к тому времени, когда наемники дошли до ставки соправителя императора Михаила IX в Пигах, вокруг них уже сложилась такая атмосфера всеобщей враждебности, что Михаил просто закрыл перед ними ворота.