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