Половецкая орда распространялась и на степную, или северо-западную, часть Тавриды, где она заняла кочевья своих предшественников Печенегов. Здесь Половцы вошли в столкновение с византийскими владениями юго-восточной, или гористой, части полуострова и нередко заставляли их платить дань, т. е. деньгами и товарами откупаться от своих грабежей. Наиболее известные византийские города и замки в той стороне были: Херсон, Сугдея, Феодосия, Символен (Балаклава), Инкерман, Мангуп, Алустон, Горсувит. Там мешались весьма разнообразные племена, обрывки разных народностей, а именно: греки, остатки готов, болгар, хазар, или черкесов, кроме того, евреи и армяне. Последние явились счастливыми соперниками греков в торговле; но в свою очередь должны были уступить первенство итальянцам, которые в течение XII века постепенно забирали в свои руки черноморскую торговлю и начали основывать свои поселения, или фактории, на восточном берегу полуострова; между прочим, Феодосия, или Кафа, подпала в особенности влияния генуэзцев. А с начала XIII века, т. е. со времени основания Латинской империи, на Черном и Азовском море, стали, преобладать соперники генуэзцев, венециане, которые особенно утвердились в упомянутой выше Тане.
Любопытны за это время, но, к сожалению, темны для нас, судьбы Корчева и Тмутаракани, которые в течение X и XI веков составляли самое южное владение русских князей. Окружающее море и близкое соседство с греческими городами сообщили этому краю важное значение, и князья Черниговские дорожили своим Тмутараканским уделом. Но с появлением половцев их связи с отдаленным владением постепенно ослабевают. После 1094 г., когда Олег Святославич перешел отсюда в Чернигов, летописи не упоминают более о Тмутаракани. Только 90 лет спустя удалые внуки Олега, Игорь Северский и Всеволод Трубчевский, пытаются мечом проложить дорогу сквозь Половецкую орду в свой родовой удел, но попадают в плен на берегах Каялы. Преградою, которую воздвигли Половцы между Черниговскою землею и Тмутараканским краем, воспользовалась ловкая византийская политика Комненов: она поспешила восстановить свое владычество над этим краем, когда-то составлявшим владение Византийской империи. По крайней мере император Мануил Комнен в 1170 году заключил договор с генуэзцами, по которому открыл им доступ во все свои черноморские порты, за исключением Русии и Матархи; следовательно он не допускал их в Азовское море. Матарха, или Таматарха, есть то же, что Тмутаракань; а под именем Русии разумеется Корчево (Керчь). Уже одно это имя свидетельствует о том, что на берегах Боспора Киммерийского долгое время господствовала Русь и существовали значительные русские поселения.
Завоевание Константинополя латинами повлекло за собою образование нескольких феодальных и самостоятельных владений на месте Византийской империи, основанных отчасти крестоносцами, отчасти греками. Кроме собственно Латинской империи, крестоносцы основали королевство в Фессалонике, гбрцогства в Афинах, Фивах, Морее и на островах; греки удержали за собою деспотство Эпирское в Европе, а в Малой Азии основали две империи, Никейскую и Трапезундскую. Во главе последней явился Алексей Комнен, внук помянутого выше императора Андроника I, умерщвленного константинопольскою чернию в 1185 г. При этом распадении Византийской империи ее Таврические владения (так наз. Заморье) достались трапезундским Комненам.
В то время когда Корсунь, Готия и Сугдея посылали свои дани и торговые пошлины в Трапезунд, Тмутараканский край подпал иному, не греческому владычеству. По некоторым признакам, здесь снова водворились соседние с Таманью князья Зихии, т. е. те же Черкесы-Хазары (Касоги наших летописей), которые владели этим краем до основания русского Тмутараканского княжества и которые даже при русских князьях составляли часть местной аристократии. По крайней мере у нас есть свидетельство одного католического миссионера из Венгрии, посетившего эти страны перед нашествием Батыя на Восточную Европу. Он говорит, что, пустившись в море из Константинополя, через 33 дня прибыл в Зихию, в город Матрику (Тмутаракань), где князь и народ называют себя христианами, имеют книги и священников греческих. У этого князя целая сотня жен. Мужчины бреют всю голову, а бороды отращивают с некоторым щегольством; только знатные люди в знак своего благородства оставляют немного волос над левым ухом. Следовательно, Греческая церковь хотя господствовала в том краю, но с значительною примесью местных языческих обычаев, судя по многоженству владетелей. Алания, лежавшая далее на восток от Зихии, по словам того же миссионера, представляла еще более смесь христианства с язычеством; она была разделена на многие мелкие княжества, которые находились в беспрерывных войнах друг с другом. Там господствовал обычай кровомщения; а драки и нападения до того были часты, что жители всякого села отправлялись на полевые работы или на рубку дров не иначе, как все вместе и вооруженные. Только воскресенье пользуется таким почетом, что каждый в этот день может ходить безопасно посреди своих врагов даже без оружия. Так же велико было здесь почитание креста: человек, не имевший при себе большой вооруженной свиты, мог беспрепятственно совершать путешествие, неся крест на конце щита.