Первые годы своего правления Михаил VIII Палеолог направлял усилия на восстановление Константинополя, пострадавшего за годы латинского господства. В столицу вернулись никейская знать и императорская администрация, вновь заселялись опустевшие городские районы, отстраивались разрушенные здания. Под патронатом императора были восстановлены фортификационные сооружения, прежде всего, морские стены, порт Контоскалион, Влахернский дворец, храмы (соборы Святой Софии, святых Апостолов, Влахернская церковь), был построен монастырь святого Димитрия, и возведена статуя архангела Михаила, которому коленопреклонённый император преподносит модель Константинополя. Стремясь упорядочить судопроизводство, Михаил VIII Палеолог издал простагму, которая вводила наказание для должностных лиц, обвинённых в ненадлежащем исполнении своих обязанностей. Михаил VIII Палеолог вернул из ссылки всех репрессированных императором Феодором II Ласкарем, возвратил им конфискованное имущество и земельные владения, сделал пронию наследственным владением, что означало победу старой родовитой военно-земельной знати. Расходы на восстановление города, содержание чиновничества и ведение войн истощали казну, вели к обесцениванию монеты (иперпера) и повышению налогового бремени на провинции. Против усиления податного гнёта вспыхнуло восстание крестьян-акритов в Вифинии (1262 г.), но императору удалось подавить его. В условиях острой конкуренции между итальянскими морскими республиками, соперничавшими за византийские рынки, императору приходилось вести политику лавирования. Так, в 1265 г., пытаясь ослабить генуэзцев, получивших значительные льготы по Нимфейскому договору, Михаил VIII Палеолог был вынужден вернуть ряд привилегий Венеции. Однако разрыв с генуэзцами оказался временным, и уже в 1267 г. они вновь получили право свободно торговать в византийских землях и основать свою факторию в Галате близ Константинополя – Перу. Эти уступки Генуе и Венеции имели негативные последствия для Византии, поскольку лишали казну налоговых поступлений и подрывали торговое могущество империи, оказавшейся в зависимости от итальянских республик. Стремясь восстановить владения империи на Балканах, Михаил VIII Палеолог вёл наступательную политику против Эпира и Болгарии. В 1262 г. византийцы заняли важные портовые города Анхиал и Месемврию и расширили свои владения на суше за счёт Болгарии. Летом 1264 г. эпирский деспот Михаил II заключил мир с Византией и признал суверенные права императора. В первые годы правления Михаила VIII Палеолога осложнилась внешнеполитическая обстановка на Востоке. Михаил VIII Палеолог состоял в союзе с монгольским ханом Хулагу, врагами которого были мамлюкский султан Бейбарс I (1260–1277 гг.) и хан Золотой Орды Берке (1257–1266 гг.). Однако, потерпев поражение от Берке в войне 1264–1265 гг. (на стороне Берке выступил и болгарский царь Константин I Тих Асень (1257–1277 гг.)), Михаил VIII Палеолог вынужден был заключить союз с Золотой Ордой и Египтом.