Одним из первых действий императора было смещение Константина Месопотамского, который в последние годы правления Исаака занимал должность, связанную с высшей административной властью, и был объектом ненависти аристократов, которые группировались вокруг дворца Алексея. Однако, вероятно, в конце 1195 г. проницательная императрица Ефросинья поняла, что дела идут столь плохо, что необходимо радикальное средство, чтобы корабль государства не пошел ко дну. Благодаря ее влиянию Месопотамский был призван на службу, так как она полагала, что лишь он один может положить конец продаже должностей и открытому расхищению казны. Когда он вернулся на свою должность, он получил на Алексея III такое же влияние, какое он оказывал на Исаака: другие льстецы обнаружили, что их затмил Месопотамский; император ценил лишь его одного. Он наблюдал за императором с чрезвычайным усердием, но тут Никита Хониат, по-видимому, имел в виду, что управление государством стало лучше под его руководством.
Представители знати и императорской семьи, которые раньше были в прибытке, были недовольны тем, что их отодвинул в сторонку выскочка. Среди тех, кто потерял власть, были зять императора Андроник Контостефан и брат императрицы Василий Каматир. Не имея возможности напасть на Месопотамского напрямую, они приняли решение нанести удар по его покровительнице – императрице. Поставив свои частные интересы выше семейных уз, они получили аудиенцию у императора в начале лета 1196 г., торжественно заявили ему о своей верности и обвинили императрицу в том, что у нее есть любовник. Они назвали некоего Ватаца, к которому императрица относилась как к сыну и которого, по их словам, она намеревалась посадить на трон. Алексей, не проведя никакого расследования, принял это голословное утверждение и отправил своего телохранителя лишить жизни Ватаца, который в то время командовал армией, воевавшей с лже-Алексеем II в Вифинии. В присутствии войск посланник приблизился к молодому полководцу и заявил, что у него секретное сообщение от императора. Отведя свою жертву в сторонку, он вытащил меч и снес военачальнику голову. Когда он привез ее императору, тот принялся катать ее по полу и глумиться над ней. Затем, ни слова не говоря императрице, он отправился в свой первый военный поход против Хрисоса.
У Ефросиньи было два месяца, чтобы узнать об обвинении и подготовиться к защите. Возвращавшегося из похода императора встречал весь двор в Афамее в нескольких километрах от города, где императрица обратилась к нему с мольбой милостиво закрыть глаза на ее проступки и умоляла доверенных лиц императора поддержать ее. Ей пригрозили изгнанием из дворца, и жизнь ее висела на волоске, так что большинство придворных жалели ее. Те из них, которые не поверили обвинению, открыто критиковали лживые утверждения клеветников, в то время как другие доказывали, что это дело надо тщательно расследовать, чтобы о позоре императора не стало известно всему миру. Поэтому Алексей отложил принятие решения и вернулся во Влахернский дворец, где он даже отобедал с императрицей, но его взгляды выдавали его сомнения. Требуя справедливости, Ефросинья торжественно заявила, что готова к любому приговору, но попросила своего мужа рассматривать правду, а не слова обвинителей. Император приказал подвергнуть пыткам нескольких женщин, прислуживающих в спальне, и евнухов и на основании их показаний приказал удалить Ефросинью из дворца. Чтобы избежать людских взглядов, ее вывели через задний двор в сопровождении двух варваров-полукровок и доставили на небольшой лодке в женский монастырь под названием Нематарея, где Босфор выходит из Черного моря.
Сторонники Ефросиньи, включая Константина Месопотамского, не прекратили своих усилий. Одних подгоняли их семейно-родственные связи, а других – вероятно, упреки и насмешки населения. Все рассчитывали на мягкую и непостоянную натуру императора. Они говорили, что он зашел слишком далеко, и утверждали, что нет иного способа решить проблемы империи, кроме как вернуть императрицу. С этой целью объединилась вся императорская семья, по словам Никиты Хониата, и Месопотамский дергал за все ниточки, имевшиеся в его руках. Ефросинью вернули спустя шесть месяцев ссылки в начале весны 1197 г., и она сразу же обрела всю свою былую власть. И хотя, как пишут, за время ее отсутствия у ее мужа появилась некоторая независимость мышления, ей удалось вновь подчинить его себе, и все дела империи оказались в ее руках. Удивительно, но она открыто не проявляла свой гнев и не предпринимала никаких тайных действий против своих недавних противников, которые причинили ей такое большое зло.