Выгоды черноморской торговли привлекли в регион Генуэзскую и Венецианскую республики. По договору, 1169 года, с византийским императором Михаилом I Комнином преимущественное право судоходства и торговли на Черном море получили генуэзцы.
В 1204 году Венеция оказала помощь крестоносцам при захвате столицы Византийской империи Константинополя, в результате чего Генуя была вытеснена из Причерноморья. В Крыму венецианцы закрепились в Солдае (Сугдее — Суроже — Судаке), которая с 1237 года управлялась венецианским консулом. Безраздельное господство Венеции в регионе продолжалось до 1261 года.
В 1261 году Генуя помогла византийским грекам вернуть Константинополь. Генуэзцы получили обратно утраченные в 1204 году привилегии, а венецианским кораблям вновь разрешили ходить черноморскими проливами. Соперничество между республикой св. марка (Венецией) и республикой св. Георгия (Генуей) в причерноморском регионе продолжалось до середины XIV веке и завершилось победой Генуи. После этого генуэзцы столетие господствовали в черноморской торговле.
В 60–е годы XIII века по договору с татарами генуэзцы основали на месте древней Феодосии свою торговую факторию Каффу. Догенуэзский период средневековой истории этого населенного пункта не освещается ни письменными, ни археологическими источниками. Топоним «Кафа» (Καφασ) — перевод неизвестен – встречается в географическом тексте 360-386 годов в списке «епархий», (т.н. областей Европы): « Епархии в Европе следующие … затем Таврический Херсонес с Кафой и Σιμβολον » (М. Шангин. Новый географический текст // ВДИ, 1938, № 4 / 5. / Кафа («Καφασ») упоминается в сочинении византийского императора Константина Багрянородного (Х век) «Об управлении империей».
Багрянородный говорит о Кафе как о местности, по которой в IV веке проходила граница между Боспором и Херсонесом. (По мнению Е. А. Катюшина — / Катюшин Е. А. Об античной Кафе // Тезисы докладов … Симферополь, 1994 / — Кафой в позднеантичную и раннесредневековую эпохи могла называться территория хоры (сельскохозяйственной округи) античной Феодосии, т.е. область, прилегавшая к городу Феодосии.)
Вероятно, позднее название «Кафа» перешло на населенный пункт, находившийся в местности «кафе». Как правило, генуэзцы не оседали на голом месте – их фактории возникали в уже существовавших поселениях. поэтому, вполне вероятно, что поселение «Кафа» существовало еще в догенуэзскую эпоху.