В половине IX в. образовалось мощное русское государство - Киевская Русь. В IX-XI вв. русское влияние на жизнь в Крыму, и особенно в восточной его части, настолько увеличилось, что Черное море в ту пору называлось Русским морем, Керченский пролив-Русской рекой, город Судак - русским именем Сурож. Впоследствии в Суроже торговали московские купцы, а в самой Москве до XX в. существовали сурожские торговые ряды, в которых в свое время, видимо, торговали товарами, привозимыми из Крыма. О жизни Феодосии в эту эпоху сведений пока нет, но надо полагать, что, находясь в ближайшем соседстве с Тмутараканью, поселением в Коктебеле и Суроже, она не могла оставаться в стороне от общего исторического и экономического развития восточного Крыма.
В первой половине XIII в. из Азии на территорию Киевской Руси вторглись самые свирепые варвары-монголы. Разорив Киевскую Русь, оттеснив русских на север, они ворвались в Крым, где все предали огню и мечу: сжигали города, грабили имущество, а жителей уничтожали или угоняли в неволю. Татаро-монголы в 1242 году основали свое государство - Золотую орду - со сто лицей на Волге. Крым первоначально управлялся наместниками Золотой орды, которые создали свою столицу Солхат (на месте нынешнего Старого Крыма).
В начале XIII в. под ударами крестоносцев пала Византийская империя. Феодальная знать западно-европейских государств в целях захвата новых земель организовала крестовые походы в страны Ближнего Востока. Отдельные отряды крестоносцев и итальянских купцов вошли в Черное море. Генуэзские купцы, учитывая исключительные удобства Феодосийской бухты, в 70-80 годах XIII в. на месте древней Феодосии устроили торговую факторию, которую наименовали Кафой. Чтобы вытеснить своих конкурентов по торговле на Черном море - венецианцев, генуэзцы построили в Константинополе сильные укрепления - Перу и Галату, закрыли доступ в Черное море всем кораблям, кроме генуэзских, и стали полными хозяевами торговых путей из Средиземноморья в страны Востока.
На месте древних поселений в Крыму генуэзцы укрепляют города Боспор (Керчь), Кафу (Феодосия), Солдайю (Судак), Гурзу-виты (Гурзуф), Чембало (Балаклава), строят здесь мощные крепости и создают свои опорные базы. Центром генуэзских колоний на Черном море была Кафа (Феодосия). Кафа лежала на стыке морских и сухопутных караванных путей из Европы на Кавказ, в Среднюю Азию, Индию и Китай. С Востока в страны Европы через Кафу везли пшеницу, соль, рыбу, икру, вино, шерсть, меха, воск, золото, серебро, драгоценные камни, пряные коренья, китайский фарфор и другие товары. В середине XIII в. Китай был сильным государством с высокой культурой, с широко развитым мореплаванием. Китайские мореплаватели открыли африканские берега в 1418 г. за восемь лет до португальцев.
Кафа была крупным транзитным пунктом торговли. Генуэзские купцы концентрировали в Кафе товары, поступавшие на их склады из Европы и Азии, и распределяли их, предпочитая находиться в городе, а не ездить в далекий и опасный путь с караванами. И все же самым прибыльным "товаром" были невольники-рабы, которых крымские ханы доставляли генуэзцам. Разбойничьи набеги с целью увода в плен невольников и грабежа стали специальностью и одним из основных источников существования Крымского ханства.
Регулярно раз, а то и два раза в год татарская орда отправлялась на разбой в русские и украинские земли и возвращалась в Крым с караванами награбленного добра и толпами пленных. Число невольников в отдельные полные ужаса набеги доходило до 50-60 тысяч человек. Прохождение их через Перекоп было настолько длительным и удручающим, что один из очевидцев, обращаясь к татарам, воскликнул: "Остались ли еще люди там, где вы были?!" Генуэзские купцы стимулировали разбойничьи набеги татар. Генуэзцы были привилегированной частью населения генуэзских колоний. Только они могли занимать высшие административные посты и освобождались от многих налогов.
Генуэзская прослойка среди населения Кафы была очень незначительна. В 1475 г. на 70 000 человек населения Кафы генуэзцев приходилось около одной тысячи. Кафа была тогда самым крупным центром работорговли во всей Европе. Это подтверждается н еоднократными письменными указаниями того времени. Крымские ханы были заинтересованы в торговле с генуэзцами и легко мирились с их владениями в Крыму. Внешне генуэзцы признавали свою зависимость от крымского ханства. Это проявлялось, в частности, и в том, что наряду с гербом Генуи (крест на щите) изображался герб ханства. На жестокой эксплуатации невольников держалось благополучие ханства и генуэзцев. Невольники строили и укрепляли города, работали в поле и садах, пасли стада. Невольничьим трудом построены крепости на месте древнегреческих городов. Развалины их, сохранившиеся до наших дней, являются мрачными памятниками насилия и жестокой эксплуатации славянских народов чужеземными захватчиками. Руками невольников строились в Кафе и дворцы знатного купечества.
Католическое духовенство во главе с римским папой открыто проявляло заинтересованность в укреплении Кафы и других генуэзских колоний в Крыму, видя в них форпост экономической экспансии и католицизма не только против татар, но одновременно против русских и украинцев. Не случайно отряды итальянских войск из Крыма принимали участие в походе Мамая на Москву. Идея крестовых походов была еще свежа в памяти римской церкви. В знак особого внимания римского папы Климента VI к судьбам Кафы одна из самых сильных башен цитадели генуэзской крепости в Феодосии была названа его именем. Она сохранилась до наших дней лучше всех остальных башен генуэзской крепости.
Башня Климента VI защищала большие ворота и калитку, ведущие в цитадель древней крепости. В южной стене башни видна прямоугольная ниша, в которой была вделана мраморная плита с большой посвятительной надписью, хранящаяся в настоящее время в Феодосийском краеведческом музее. Над этой нишей хорошо сохранилась другая, стрельчатая, в которой, вероятно, был укреплен барельеф с каким-нибудь изображением на религиозную тему.