Внутренняя оппозиция, а особенно устранение ее возможных будущих лидеров, также занимали мысли Андроника. Принцесса Мария Порфирородная проявила себя как человек, способный организовать заговор против бывшего правителя. У нее были последователи среди жителей Константинополя, которые соперничали со сторонниками Андроника. Вдобавок она была близкой родственницей императора, и у нее было больше прав на корону, чем у регента. Поэтому ее и ее мужа Ренье-Иоанна Монферратского всегда держали во дворце, хоть и обращались с ними уважительно и гуманно. Однако впоследствии они умерли: кесарь вскоре после своей супруги. По слухам, которым не полностью доверяет даже Никита Хониат, евнух Птеригионит давал им медленно действующий, подрывающий силы яд; с этой целью его и подкупил Андроник.
Другую опасность представляла императрица-мать Мария-Зена Антиохийская, которая могла однажды задумать освободить Алексея II от контроля со стороны Андроника. В присутствии знати он обвинил ее в заговоре против государства, настроил против нее население и получил согласие патриарха Феодосия на ее изгнание из дворца. Прежде чем осуществить это решение, Андроник поинтересовался мнением судей велума, которые входили в главный судебный орган империи. Трое судей (Деметрий Торник, Лев Монастериот и Константин Патренос), которые в то время находились в оппозиции к Андронику, спросили его, по распоряжению ли императора Марию-Зену удаляют из дворца, тем самым ставя под сомнение действия регента. Андроник пришел в ярость и вскричал: «Это люди, которые подстрекали протосеваста к жестоким поступкам! Схватить их!» Но прежде чем охрана сумела выполнить приказ, стоящая рядом толпа окружила трех судей и избила их до полусмерти. Марию-Зену немедленно выслали в монастырь Святого Диомеда.
До сих пор Андроника поддерживала большая часть придворной знати, ненавидевшей протосеваста; фактически его успех зависел от того, что на его сторону переметнулись Андроник Ангел и мегадука Андроник Контостефан. Очевидно, удаление из дворца императрицы-матери встревожило этих людей, так как в этот момент сформировался заговор. Его возглавили двое вышеупомянутых людей, их сыновья и логофет дрома (министр иностранных дел) Василий Каматир Дука; но к заговору примкнули и многие другие. Андроник быстро раскрыл заговорщиков и послал солдат схватить виновных магнатов. Среди схваченных оказались Контостефан, четверо его сыновей и Каматир; они были ослеплены. Многих посадили в тюрьму, и некоторые из них были позднее ослеплены, но Андронику Ангелу и шестерым его сыновьям удалось скрыться на корабле, нагруженном пустыми кувшинами, на котором они бежали в Сирию, где отец умер; его сыновья стали непримиримыми врагами Андроника Комнина.
История Марии-Зены на этом не закончилась. Раскрытие заговора заставило многих из тех, которые, возможно, были вовлечены в него на периферии, внезапно стать пылкими сторонниками нового режима. Чтобы показать свое рвение, они требовали крови императрицы-матери. Ее обвинили в том, что она написала своему деверю – королю Венгрии Беле III и предложила ему вторгнуться в Балканские провинции. Андроник издал указ о казнях предателей империи, который подписал Алексей II. Согласно его положениям, регент принял решение лишить Марию-Зену жизни. Для исполнения приговора Андроник выбрал своего сына Мануила и брата своей жены – севаста Георгия, но они отказались, сказав, что не одобряют казнь. Это был лишь первый из нескольких случаев, когда Мануил открыто воспротивился жесткому курсу, взятому его отцом. Разгневанный такой осторожной позицией членов собственной семьи, Андроник передал это поручение своим ставленникам Константину Трипсиху этериарху (начальник личной охраны императора) и евнуху Птеригиониту. Они утопили Марию-Зену, чьи красота и несчастья тронули даже здравомыслящего Никиту Хониата настолько, что он выразил свое сожаление по этому поводу.