К 1116 году половцы стали единственными хозяевами степей Северного Причерноморья. Они контролировали бóльшую часть территории Крыма, кроме Керченского полуострова и Херсонеса. Их главным городом стал Судак, называвшийся тогда Сугдеей. Именно в нем сосредоточилась бóльшая часть торговли русскими товарами и предметами роскоши из Европы, Индии и Китая. Кроме того, в Сугдее располагался крупный невольничий рынок. Богатства Сугдеи привлекли внимание сельджукида Ала-ад-дина Кей-Кубада, властителя расположенного в Малой Азии Румского султаната. Он высадил свои войска в Крыму под предлогом того, что в Сугдее обидели сельджукских купцов. Отряд сельджуков во главе с эмиром Хюсамеддином Чобаном разгромил войско русичей и половцев, составлявшее гарнизон Сугдеи. Город был захвачен, в нем расквартировался султанский гарнизон, находившийся здесь до татарского погрома 1239 года.
Половцы так и не создали государство в европейском понимании, они продолжали жить родовыми кланами, нередко враждуя друг с другом. Их охотно нанимали на службу как русские князья, так и восточные владыки, многие из которых породнились с половцами, взяв в жены дочерей их вождей. Время половцев закончилось в 30-х годах XIII века с вторжением в Восточную Европу монголо-татар. У половцев была давняя вражда с этим народом, поэтому их большая часть снялась с насиженного места. Племена, породнившиеся с русичами, отправились в русские земли. Орду половцев под предводительством хана Котяна, тестя князя Даниила Романовича Галицкого, принял венгерский король Бела IV и, дабы покрепче привязать к себе этих воинственных людей, обручил наследного принца Стефана V с дочерью половецкого хана. Часть половцев ушла в Закавказье и Малую Азию, часть отправилась в Египет, пополнив ряды воинов-мамлюков. Те же, кто остался и пережил первые битвы с монгольскими завоевателями, в конце концов влились в их ряды. Так образовался тюркоязычный этнос, известный с XIV века как ногайцы. Вот что рассказывает о слиянии монголов и половцев арабский автор XIV века Эль-Омари: «В древности это государство (Золотая Орда) было страной кипчаков, но когда им завладели татары (монголы), то кипчаки сделались их подданными. Потом они (монголы) смешались и породнились с ними (кипчаками) и земля одержала верх над природными и расовыми качествами их (монголов), и все они стали точно кипчаками, как будто они одного (с ними) рода, оттого что монголы поселились на земле кипчаков, вступали в брак с ними и оставались жить в земле их (кипчаков)».
Улицы древнего Херсаонеса © В. Бысов, 2005
В «византийской» части Крыма тоже произошли важные события. После того как 13 апреля 1204 года столицу Византии Константинополь штурмом захватили и разграбили крестоносцы, контроль Византии над ее крымскими территориями был утрачен. На обломках великой державы были созданы Никейская империя на западе Малой Азии и Трапезундская империя в северной части Малой Азии, у Черного моря. Херсонес начал платить дань Трапезундской империи, однако ее власть на Крымском полуострове была номинальной. В это время Херсонес разбогател благодаря фактическому самоуправлению, в него охотно переселялись богатые купцы и квалифицированные ремесленники. Херсонес становится самым большим городом Крыма с населением в пять тысяч жителей.
Долина Демерджи. Худ. К. Боссоли. 1856 г.
В середине XII века на юго-западе Крымского полуострова богатым византийским ссыльным из аристократического армянского рода Гаврасов Константином было создано Мангупское княжество Феодоро. Это было многонациональное сообщество, в него входили аланы, греки, готы, тавры и потомки кочевников. Границы княжества проходили по черноморскому побережью от Балаклавы до Алушты, а на севере простирались до реки Качи. Столицей Феодоро был город Мангуп, бывшая готская крепость, расположенная в семнадцати километрах от современного Бахчисарая. Вторым крупным городом княжества стала крепость Фуна, построенная у подножья горы Демерджи, в которой новоявленный князь поселил свою семью. В 1427 году на месте пещерного города Инкермана (расположенного рядом с современным Севастополем) феодорийцы построили крепость Каламиту, защищавшую единственный морской порт княжества в устье реки Черной. Княжество Феодоро вступило в конфронтацию с генуэзскими торговыми кланами, и в 1434 году войска Генуи захватили Каламиту и сожгли ее. Однако богатый князь в рекордные сроки восстановил крепость. Небольшое, но процветающее княжество быстро вышло на политическую арену и установило обширные международные связи. Несколько попыток захватить его со стороны турок и монголо-татар потерпели поражение, но в 1475 году княжество перестало существовать, полностью уничтоженное турками.