В обычных обстоятельствах тело императора, умершего за пределами Константинополя, должно было быть привезено и захоронено в одном из главных храмов столицы. Предполагалось, что Михаил VIII будет погребен в монастыре Святого Димитрия, который он восстановил. Однако по приказу Андроника тело Михаила было доставлено в ближайший к месту его смерти монастырь и захоронено там. А следующей весной его перенесли в монастырь в Силимврии, тот самый, в котором 20 лет назад был погребен скелет Василия II. Не было никаких публичных похорон в Константинополе, и почивший император не поминался на литургии в годовщину его смерти, как это было принято. Через несколько дней после смерти отца Андроник распорядился выпустить из тюрем всех заключенных за сопротивление Лионской унии, вернуть отправленных в ссылки и низложил патриарха Константинопольского Иоанна XI, которого Михаил назначил, чтобы тот выполнил условия соглашения с Папой. В следующем апреле были низложены и заменены и все епископы, которые поддерживали унию. Новый император фактически отказался от непопулярного соглашения, даже в ущерб памяти своего отца. Теперь, когда угроза нападения со стороны Запада стала явно меньше, поскольку Карл Анжуйский вынужден был сопротивляться вторжению Педро Арагонского на Сицилию, в унии уже не было необходимости. Кроме того, отказ от нее, несомненно, принес Андронику любовь всего народа: ликующие толпы приветствовали на улицах столицы освобождение заключенных и восстановление православия.
Андроник надеялся также остановить отчуждение провинций и добиться популярности и там. Он посетил крепость, где все еще томился в заточении несчастный Иоанн IV Ласкарис, которому было на тот момент около 40 лет и которого до сих пор некоторые считали законным императором. Андроник попросил у Иоанна прощения за преступление своего отца и просил также признать его в качестве императора. Оттуда он отправился в старую столицу Ласкарисов Никею. В Малой Азии Андроник провел три года, укрепляя защиту границ от турок. К апрелю 1299 года он был в Фессалониках и в следующем году посетил город Монемвасия в изолированном византийском анклаве на юге Пелопоннеса. Он считается основателем церкви Святой Софии, которая стоит на вершине скалы с видом на море. Даже жену себе Андроник выбрал такую, чтобы пресечь сепаратистские тенденции в провинциях. В 1284 году его второй супругой стала Ирина Монферратская, итальянка, принадлежавшая к тому же семейству, что и Бонифаций Монферратский, который правил королевством Фессалоники с 1204 по 1207 год. Частью брачного соглашения было то, что семья Ирины навсегда откажется от своих притязаний на Фессалоники. Андроник, несомненно, знал, что в 1204 году жители Фессалоник приветствовали латинян.