Рубеж веков стал для Византии временем непрекращающихся бед, а Андроник явно был не в состоянии остановить ускоряющийся упадок. К тому же Константинополь стал одним из главных полей сражения, на котором разрешали свои разногласия Генуя и Венеция. В июле 1296 года венецианский флот подошел к входу в Босфор и совершил жестокое нападение на генуэзскую колонию в Галате; когда же вмешался византийский гарнизон, венецианцы стали стрелять по самому городу и сожгли все греческие дома в пределах досягаемости. В декабре генуэзцы устроили контратаку, разрушив главные здания и убив всех выдающихся венецианцев в городе. Следующим летом приплыл новый венецианский флот и привез личное послание дожа, в котором тот обвинял императора в поощрении поведения генуэзцев, возлагал на него ответственность за причиненный ущерб и требовал компенсации. Флот прорвался в Золотой Рог и поджег одну из императорских галер, а потом вернулся в Венецию, захватив в плен множество генуэзцев.

В 1299 году Венеция и Генуя заключили сепаратный мир, однако венецианцы по-прежнему настаивали на компенсации и летом 1302 года напали на Константинополь третий раз за семь лет. Они снова вошли в Золотой Рог, подожгли все византийские здания в пределах досягаемости, а потом заняли остров Принкипо в Мраморном море; в то время он использовался в качестве лагеря для беженцев из Анатолии, и венецианцы грозились их всех перебить, если император не выплатит им долг. Андроник уступил, а кроме того, согласился подписать десятилетний договор, подтверждавший все привилегии венецианцев в Константинополе.

1302 год стал ужасным для Византии. Ранней весной сын и соправитель императора Михаил IX потерпел поражение в битве с турками при Магнесии и едва избежал смерти. Далее последовало нападение венецианцев, а всего через несколько недель после него, 27 июля, византийская армия столкнулась неподалеку от Никомедии с турецким войском, численность которого была выше в два с лишним раза, под командованием эмира по имени Осман. Битва была не особенно кровопролитной, однако прояснила намерения Османа. Он и его люди двигались на юго-запад вдоль побережья Мраморного моря, пока не дошли до Эгейского моря. Таким было первое появление человека, который начал карьеру как правитель одного из самых маленьких эмиратов в Анатолии, а затем основал династию, давшую имя Османской империи. И в том же 1302 году Андроник Палеолог получил сообщение от Рожера де Флора, предводителя Каталонской дружины.

Каталонская дружина была по сути группой профессиональных испанских наемников, большинство из которых происходили из Каталонии; в 1281 году их нанял Педро III, чтобы использовать в североафриканских и сицилийских кампаниях. Говорят, что Рожер де Флор был сыном Рихарда фон Блюма, немецкого сокольничего Фридриха II. В возрасте восьми лет он пошел служить на галере у тамплиеров, а затем стал чрезвычайно удачливым пиратом; позже он предложил свои услуги сыну Педро Федериго, который немедленно назначил его адмиралом. Рожер быстро проявил себя как храбрый боец на море и на суше и обзавелся верными последователями. Так и появилась Каталонская дружина.