В 1256 году Феодор II заключил мирный договор с Болгарией, и отношения между двумя государствами стали еще лучше, когда вскоре после этого царь Михаил Асень был убит и его сменил боярин Константин Тих, женившийся на дочери Феодора Ирине. Был заключен и еще один династический брак – между дочерью Иоанна Марией и Никифором, сыном деспота Эпира Михаила II. К сожалению, этот брак привел к обратным результатам, так как в последнюю минуту Феодор неразумно потребовал себе Дураццо и македонский город Сервию. Мать жениха, сопровождавшая сына в императорский лагерь в Марице, запугали и заставили подписать это соглашение; однако, когда по возвращении она рассказала мужу, что отдала два самых важных его города, он немедленно организовал яростную кампанию против Фессалоник, уговорив сербов и албанцев оказать ему поддержку. Через несколько дней восстала вся Македония.

Человеком, который лучше всех смог бы справиться с этой ситуацией, был молодой военачальник по имени Михаил Палеолог; однако император всегда с завистью относился к красивому молодому аристократу, который, казалось, обладал всеми теми талантами, которых не было у Феодора. Кроме того, он ему не доверял. Ранее он совершенно неоправданно обвинил его в государственной измене и так ему угрожал, что Михаил был вынужден искать спасения у сельджуков. После этих событий Михаил принес императору клятву верности, но Феодор лишь с большой неохотой доверил ему командование. Вероятно, он опасался, что военачальник может восстать против него, и потому дал ему слишком малое войско, чтобы оно могло принести какую-то пользу. Михаил и его люди храбро сражались и дошли до самого Дураццо, но так и не смогли остановить восстание. К лету деспот уже стоял у ворот Фессалоник, а Михаил Палеолог, лишенный звания и вскоре отлученный от церкви, томился в никейской тюрьме. Столь постыдное обращение с выдающимся полководцем укрепило народ Никеи в убежденности, что их василевс больше не может править империей разумно, и военный переворот был бы неизбежен, если бы Феодор внезапно и очень кстати не умер от своей болезни в августе 1258 года в возрасте 36 лет. Поскольку его старший сын Иоанн был еще ребенком, он назначил регентом ненавистного Георгия Музалона. На смертном одре он заставил ведущих представителей аристократии поклясться в верности Иоанну и Георгию, однако во время заупокойной службы, которая состоялась через девять дней, они убили Музалона прямо у главного алтаря и разрубили его тело на куски. Последовал дворцовый переворот, в результате которого регентом назначили второпях освобожденного Михаила Палеолога (который, возможно, и организовал заговор).