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