В период раннего средневековья на развалинах древнегреческой Феодосии возникло новое поселение — Кафа. Под этим названием в X в. его упоминает византийский император и писатель Константин Багрянородный.
Начиная с VIII — IX вв. в Таврике, особенно в прибрежной и горной ее части, заметно усиливается влияние византийских греков: этому способствовал приток эмигрантов-иконопочитателей, искавших убежища на окраинах империи. А век XIII ознаменовался господством на море генуэзцев, на суше — татар.
Территория Феодосии вошла в состав Крымского улуса (провинции) Золотой Орды. Во второй половине XIII в. (точнее, в семидесятые годы) генуэзские купцы приобрели у татарского хана Оран-Тимура участок побережья Феодосийской бухты и основали здесь свою факторию, сохранив за ней уже известное название Кафа.
Благодаря выгодному географическому положению Кафа вскоре превратилась в крупный транзитный центр международной торговли и опорный пункт генуэзских колоний в Причерноморье.
Через Кафу в Европу вывозились пшеница, восточные пряности, золото и драгоценные камни, соль, рыба, икра, шерсть, меха, воск и другие товары. Важной статьей генуэзской торговли были рабы, захваченные татарскими феодалами во время разбойничьих набегов на русские, украинские, польские земли и Северный Кавказ.
Исторические документы свидетельствуют о том, что в XIII — XV вв, Кафа являлась центром работорговли в бассейне Черного моря. Кафинекий невольничий рынок оставался местом наживы и позднее. И при генуэзцах, и при турках шел бойкий торг.
Заморским купцам предоставлялась возможность выбирать «живой товар» по душе: коренастые, крепкие невольники — для работы; рослые, сильные мужчины — для выгодной перепродажи в гвардию монархов и полководцев далеких стран. Многих мужчин продавали на галеры, где их навсегда приковывали к веслам.
Девушек покупали для гаремов, женщин постарше — для работы в домах купцов и знатных граждан.
Очень высоко ценились женщины с грудными детьми: русские и украинские полонянки считались лучшими кормилицами детей знатных особ.
Маленькие дети, ничего не ведающие о своей судьбе, также считались выгодным товаром: из них воспитывали надежных телохранителей.