Однако вскоре он навлёк на себя гнев самого императора. Андроника, управлявшего Враницовой и Белградом, обвинили в том, что он тайно соединился с сербами и условился с их вождём лишить Мануила власти. В оковах его препроводили в Константинополь и заключили в одной из башен Большого дворца, где он провёл довольно долгое время, не переставая искать путей для бегства. Наконец Андроник притворился больным, и ему назначили в услужение молодого наёмного слугу из иностранцев, плохо говорившего по-гречески. Этому слуге Андроник поручил унести потихоньку ключи от дверей башни в то время, когда стража, порядочно подвыпив, уснёт после обеда, и с этих ключей сделать из воска точные слепки. Слуга исполнил приказание и передал слепки сыну Андроника Мануилу. Мануил сделал из меди такие же ключи и переслал их отцу в амфоре с вином вместе с льняной верёвкой, клубком ниток и тонкими шнурками. Ночью Андроник отпер все замки и с верёвкой в руках вышел из темницы. Остаток ночи и два следующих дня он провёл в густой и высокой траве, которой поросли некоторые места дворцового двора. Когда искавшие его угомонились, Андроник устроил из палок лестницу и, спустившись со стены между двумя башнями, сел в лодку, ожидавшую его здесь по уговору. Едва они отплыли от берега, их задержала вуколеонская стража. Однако удивительная изобретательность спасла Андроника и на этот раз. Сменив греческий язык на варварский, он изобразил из себя беглого раба, которого хозяин везёт после наказания. Его сообщник подкупил стражу дарами и был отпущен. Добравшись наконец до берега, Андроник смог избавиться от кандалов. Домашние снабдили его лошадью и подорожными документами. Из столицы он отправился во Фракию. Конечной же целью его была Русь, где Андроник надеялся получить убежище и защиту. Ему удалось благополучно проехать большую часть пути, но в Болгарии его опознали и заключили под стражу. Зная, что Андроника разыскивает император и надеясь на большую награду, несколько болгар повезли его обратно в Константинополь. Чтобы обмануть своих стражников, Андроник притворился, что страдает поносом. Он часто сходил с лошади, отходил от спутников и готовился к отправлению естественной нужды. Много раз он проделывал это днём и ночью и наконец обманул своих стражей. Однажды, поднявшись в темноте, он воткнул в землю палку, на которую опирался в дороге как человек больной, надел на неё хламиду, положил сверху шляпу и таким образом сделал нечто похожее на присевшего человека. Предоставив стражам наблюдать за этим чучелом, он тайком пробрался в росший неподалёку лес и бросился бежать. Наконец он добрался до Галицкого князя Ярослава Осмомысла, был принят им с распростёртыми объятиями и прожил у него несколько лет. В 1165 году Мануил, считая длительное отсутствие двоюродного брата опасным для себя, вызвал его в Константинополь и примирился с ним.
В 1166 году Мануил назначил Андроника правителем Киликии и отправил в Тарс. Здесь он часто вступал в битвы с Торусом, владетелем Армении, но потерпел от него несколько поражений. Вскоре, однако, Андроник отвлечён был от ратных подвигов новым романом: он вступил в связь с Феодорой, вдовой иерусалимского короля Балдуина и родной племянницей императора Мануила. Рассерженный император отправил правителям Сирии приказ схватить Андроника и лишить его зрения. Но грамота эта попала к Феодоре, которая предупредила своего любовника об опасности. Вместе они бежали из Иерусалима и после долгих странствий добрались до Салтуха, султана Колонии (в Каппадокии). Здесь он поселился с Феодорой и двумя прижитыми от неё детьми — Алексеем и Ириной. Мануил много раз пытался заполучить Андроника, но все его попытки были безуспешны. Наконец в 1177 году при помощи Никифора Палеолога, владевшего Трапезундом, императору удалось захватить Феодору. Тогда Андроник, увлекаемый страстной любовью к ней и детям, отправил к Мануилу послов и просил прощения за все свои поступки. Мануил разрешил ему вернуться. Перед тем как явиться к императору, Андроник надел на шею тяжёлую цепь, спускавшуюся до самых пят, и скрыл её до времени под одеждой. Допущенный к трону, он тотчас растянулся на полу во всю длину своего огромного роста и со слезами на глазах пламенно и трогательно попросил прощения. Мануил, изумлённый этим зрелищем, прослезился и приказал поднять его. Но Андроник встал не прежде, чем его протащили за цепь по ступеням престола. Вследствие этого Андроник был прощён, принят блистательным образом и удостоился великолепного угощения. Потом его переправили в Эней, с тем чтобы он поселился там и отдохнул от бродячей жизни.