Пока решительные действия его жены обеспечивали положение нового правителя в Константинополе, тот возвращался не спеша. Раздав средства, предназначенные для ведения войны, в качестве вознаграждений своим сторонникам, он теперь раздавал владения империи, государственные доходы и титулы, подписывая все бумаги, какие бы ни клали перед ним, независимо от того, о каком даре или уступке в них шла речь. Пока он таким образом завоевывал на свою сторону аристократию и чиновничество, он также занимался пропагандой, утверждая, что под угрозой смерти со стороны армии он был вынужден принять корону вопреки своим собственным желаниям. А чтобы поднять свой авторитет, он изменил свою фамилию с Ангела на Комнина. Как только он достиг Внешнего Филопатиона у стен Константинополя, он устроил большой прием, на который пришли все, кроме нескольких сановников города, чтобы принести ему присягу. Затем состоялась его коронация в Святой Софии, но она сопровождалась дурными предзнаменованиями. Конь, которого подвели ему, чтобы ехать из храма, оказался слишком норовистым; когда его успокоили и император сел на него, конь тут же встал на дыбы, императорская корона упала, а император чуть не свалился с седла. Во время шествия мул, на котором сидел дядя императора Иоанн (Ангел) Дука севастократор, неожиданно вздрогнул, и корона севастократора упала с его головы, обнажив его лысину, что развеселило толпу. Иоанн, однако, сумел продолжить путь под смех толпы. Правление началось неблагоприятно.
Алексей III взошел на трон благодаря группе недовольных аристократов, но за более действенной помощью, особенно в часто случавшиеся критические моменты, он обращался к своей семье и близким родственникам. Самой прочной опорой власти была императрица Ефросинья Дукиня Каматира, так как практически во всем ее муж был слабым, а она сильной. Она обладала решительным умом, умением управлять делами и натренированным языком, чтобы направлять императора в государственных делах. Когда прибыл какой-то посол, она сидела во всех регалиях рядом с Алексеем, а на официальных церемониалах перед ней склонялись ниже, чем перед самим императором, так что фактически, по утверждению Никиты Хониата, теперь в империи было два правителя. Она без зазрения совести продвигала по карьерной лестнице своих родственников – и не всегда с удовлетворительными результатами. Руководствуясь суевериями, она приказала срубить морду калидонского кабана, украшавшую Ипподром, и лишить лица другую статую, которая, по ее мнению, символизировала злые силы. В народе она не пользовалась любовью; тем не менее, когда какие-то пошляки научили птиц кричать в ее адрес мерзкие слова, она проигнорировала это публичное оскорбление и поехала на охоту. Ее сила и способности были бесценны для императора.
У Алексея был широкий и неопределенный круг родственников. Все его братья были ослеплены или умерли, а из его сестер упоминается только Феодора – брошенная жена Конрада Монферратского, которая в 1195–1198 гг. превратила мужской Далматский монастырь в женский, очевидно, для того, чтобы найти в нем уединение. О присутствии Иоанна (Ангела) Дуки севастократора на коронации уже было упомянуто. До самой своей смерти где-то в 1200 г. он, по-видимому, играл важную роль в управлении империей, ожесточенно соперничая с сыном своей сестры Мануилом Камицей протостратором, чьи богатства, способности и родство с императором давали ему право претендовать на то, чтобы быть назначенным наследником Алексея III.
Вопрос о престолонаследии вызвал огромные затруднения в семье императора. Так как у Алексея и Ефросиньи было три дочери и ни одного сына, огромную важность имели личность и ранг зятьев императора. В начале его правления все принцессы состояли в удовлетворительных браках. На коронации императора сопровождали мужья двух его старших дочерей – Андроник Контостефан и Исаак Комнин севастократор – отпрыск неизвестной ветви семьи Комнинов; но к 1197 г. оба они умерли: первый – от естественных причин, а последний – от лишений, перенесенных им в плену у валахов. Исаак Комнин оставил юную дочь Феодору, которой, в конечном счете, суждено было стать политической пешкой императора. Тем временем развернулось яростное соперничество за то, чтобы быть выбранным наследником Алексея III. Кандидатами, имевшими больше шансов, были сыновья трех братьев Алексея и его зятя Иоанна Кантакузина кесаря; и всех их Никита Хониат обвиняет в вопиющей праздности и использовании всевозможных уловок, чтобы добиться благосклонности императора. Но никого из них Алексей III не выбрал. Вместо этого для своей старшей дочери Ирины (вдовы Контостефана) он выбрал в мужья Алексея Палеолога, которого заставил развестись с красавицей женой; а для дочери Анны он выбрал Феодора Ласкариса. Семья Палеолог была уважаема на протяжении всего периода правления Комнинов, однако о предках Ласкарисов ничего не известно. Двойная свадьба, отпразднованная с большой пышностью весной 1199 г., была важным событием для будущего: после 1204 г. Феодор Ласкарис положил начало возрождению империи в г. Никее, а у Алексея Палеолога с Ириной Ангелиной появилась дочь Феодора, ставшая матерью Михаила VIII Палеолога. На тот момент император считал своим наследником Алексея Палеолога, который верно служил ему в качестве полководца.