После смерти Романа пришла очередь Олега. Практически вся его дружина полегла на Нежатиной Ниве, князь оказался без защиты перед лицом опасности: «Олега Святославовича хазары схватили и отправили за море в Царьград» (4, 202). Хазары явно действовали по указке из Киева, на это указывает прибытие в Тмутаракань посадника Ратибора, доверенного человека Всеволода. Как и место, куда отправили Олега, – Константинополь. У Всеволода, женатого первым браком на византийской принцессе, были хорошие связи при императорском дворе, чем он в данном случае и воспользовался. Византийские чиновники отправили Олега в ссылку на остров Родос.
Князь-изгой не собирался мириться со своей участью и женится на знатной гречанке Феофано Музалон. Косвенно на это указывает найденная в XIX в. печать, где по-гречески было написано: «Господи, помоги своей рабе Феофано, архонтиссе Росии Музалониссе». По мнению С.Э. Цветкова, версия о женитьбе Олега на представительнице рода Музалон «основана на сопоставлении легенды этой печати с данными Любецкого синодика, упоминающего «князя Михаила [церковное имя Олега] Черниговского и княгиню его Феофану». Предполагается, что обе Феофаны – это одно и то же лицо». (89, 477). Действительно, в Любецком синодике есть раздел, посвященный черниговским князьям, где упоминается князь Михаил и его жена Феофано (47, 24). Благодаря помощи влиятельных родственников жены Олег сумел в 1083 г. возвратиться в Тмутаракань. Причем вернулся как ставленник византийского императора: «Олег Святославич был поставлен на тмутараканский престол греками, видевшими в нём собственного вассала, а в Тмутараканской земле – своё окраинное владение. Княжество к тому времени де-факто не относилось к сфере влияния Киевской Руси: император Алексей I Комнин, правивший в 1081–1118 гг., фигурирует в византийских документах как «присоединивший к империи Боспор Киммерийский». Печати Олега Святославича хранят надписи с греческими титулами «севаста Михаила самодержца» и «архонта Михаила, Зихии и всей Хазарии», а его жены – с надписью «Господи, помоги рабе своей Феофано Музалон, архонтиссе России». Греческие титулы Михаила архонт и севаст предполагают его прямую вовлеченность в должностную иерархию Византийской империи в качестве наместника одной из областей. Разумеется, при таком вассальном положении Тмутараканского княжества не только печати, но и монеты князя должны были соответствовать имперскому стандарту» (31, 27–28). Любая попытка Всеволода выбить племянника из Тмутаракани неминуемо вела к конфликту с Византийской империей.
К моменту появления Олега в Тмутаракани ситуация в регионе изменилась. 18 мая 1081 г. город был захвачен родственниками византийского изгоя – Давыдом Игоревичем, сыном Игоря Ярославича Волынского, и Володарем Ростиславичем, сыном князя Ростислава Владимировича Тмутараканского, отравленного византийцами. Один приходился Олегу двоюродным братом, другой двоюродным племянником. Посадник Ратибор по приказу князя был схвачен и брошен в темницу. С родственниками Олег так же не стал церемониться, поскольку Тмутаракань была наследственным уделом Святославичей. Князь выгнал из города непрошеных гостей и занялся наведением порядка в уделе. Хазар, некогда выдавших его византийцам, Олег приказал всех перебить. Князь понимал, что сил для борьбы за Чернигов у него нет, поэтому задержался в Тмутаракани надолго, вплоть до 1094 г., выжидая удобного момента, чтобы предъявить права на наследство отца.