Незадолго до смерти Потемкин лично даровал черноморцам Таманский полуостров, который отделен от Крыма Керченским проливом. Казачья старшина возложила свои надежды на получение этой земли. В 1792 году в Петербург отправляется депутация черноморцев во главе с Антоном Головатым. Выбор Головатого в руководители ответственной миссии был не случаен. Войсковой судья обладал всеми необходимыми знаниями и опытом. Он учился в Киево- Могилянской академии и бывал ранее в Петербурге. Четыре месяца Головатый добивался положительного решения главного в своей жизни дела. Известный историк кубанского казачества Федор Щербина писал, что Головатый «пустил в ход все: и знакомство с людьми сильными, и малорусскую песню, и чудачества казака-малоросса». Наконец, государыня императрица благосклонно отнеслась к прошению казаков и даровала им Тамань с правым берегом Кубани от устья до Усть-Лабинского редута. Как и прежде, от казаков правительство ожидало честной службы: «бдительно хранить пограничную линию от набегов закубанских горцев, соблюсти имя храбрых воинов и заслужить звание добрых и полезных граждан».
Пока Головатый покорял Петербург, предприимчивые казаки отправили экспедицию для осмотра Тамани и близлежащих земель. Возглавил группу казачьих первопроходцев войсковой есаул Мокий Гулик. Казаки признали землю пригодной для жизни и ведения хозяйства.
Триумфальное возвращение Головатого было широко отпраздновано. Черноморские казаки наконец-то обрели новую родину, до которой, правда, еще нужно было добраться. Их переселение на Кубань проходило в 1792–1793 годах. Черноморцам было жаль расставаться с уже заведенным за Бугом хозяйством и нажитым имуществом. Но времени устроить все дела как надо — не было. Атаман Чепега призвал всех переселяться как можно скорее. Казаки отправились на Кубань двумя группами. Первая, предводительствуемая полковником Саввой Белым, прибыла к новому месту морем на гребной флотилии. Вторая, ведомая самим Чепегой, пришла сухим путем. Головатый некоторое время оставался за Бугом, пытаясь устроить дела семейных казаков.
В первую волну заселения на Кубань переселилось 17 тысяч человек, но уже в 1795 году черноморцев стало около 25 тысяч. Из этого числа подавляющее большинство составляли мужчины. В 1802 году на каждую сотню мужчин казаков-черноморцев приходилось всего 39 женщин. Без представительниц прекрасного пола казак не мог рассчитывать не только на благоустроенное хозяйство, но и просто на продолжение казачьего рода. Женский дефицит преодолевался в Черномории тяжело. Еще в 1809 году министр внутренних дел Алексей Куракин, понимая всю сложность положения казаков, инструктировал екатеринославского губернатора (Екатеринослав — ныне город Днепр): «из числа семейств, желание свое к переселению объявивших, по уважению малого числа женского пола, ныне в Черноморском войске состоящего, предпочитать те, где более девок и вдов, в брак еще вступить могущих». Такие же проблемы испытывали казаки терские, которые даже заимствовали у горцев обычай умыкания невест.
О жизни черноморцев в новом краю историк казачества Прокофий Короленко писал так: «В первое время поселения черноморцев на Кубани житье их было не завидное. Пустынный край неприветливо встретил забугских переселенцев. Они терпели крайний недостаток во всем необходимом для первоначального обзаведения оседлой жизни в степном и безлюдном крае; несли тяжелую, по малолюдству войска, службу; страдали от болезней в новом климате и долго боролись со всякого рода лишениями».
Закубанские соседи казаков — горцы-черкесы помогали новоселам. Автор дореволюционного учебника «Кубанские казаки», предназначавшегося для учеников станичных школ Кубанской области, Антон Певнев писал: «Закубанские горцы весьма дружелюбно встретили появившихся на Кубани черноморцев. Видя, что черноморцы терпели большие невзгоды и нуждались в хозяйственных вещах, горцы на первых порах пришли к ним на помощь». Казак и горец наладили тесные, дружеские отношения. Взаимные посещения казачьих куреней и горских селений стали традицией для добрых соседей. Общаясь с горцем, казак перенимал его одежду, узнавал о подходящих для здешних мест способах ведения хозяйства. Но все изменилось в один трагический день.
Пока в Европе всех поражали события Великой французской революции, у горцев (адыгов) Северо-Западного Кавказа случилась собственная революция. В 1792 году горцы Шапсугии подняли восстание против своих аристократов, лишили имущества и изгнали их. Вскоре революция захватила и земли абадзехов. Местные князья и дворяне также вынуждены были отправиться в эмиграцию. Аристократы-изгнанники нашли приют у бжедугов, которые крепко держались старины и почитали свое дворянство. Горцы-эмигранты не смирились с незавидной ролью изгоев. Организовавшись в сильные отряды, они совершали набеги на селения отказавшегося от них народа. Развернута была и дипломатическая работа. Шапсугская и бжедугская аристократия обратилась за помощью к России. В Петербурге кавказскую политику выстраивали, ориентируясь прежде всего на местную элиту. С отдельными представителями знати всегда было легче договориться, чем с непредсказуемыми народными собраниями горцев. Казакам-черноморцам поручили оказать военную поддержку горскому дворянству. Черноморцы повиновались. Времена вольного казачества прошли безвозвратно, настала пора тяжелой царской службы.
29 июня 1796 года — памятная дата в истории адыгов. Это день Бзиюкской битвы (Бзиюко-зау). Бзиюк — название небольшой речки, на берегах которой горцы сошлись в решающей схватке. Поначалу успех был на стороне народного ополчения шапсугов и абадзехов. Их конница сильно потеснила строй аристократов, едва сдерживавших безудержный натиск их бывших подданных. В самом начале боя был смертельно ранен знаменитый среди адыгов Баты-Гирей — предводитель гордых бжедугов. Это еще больше смутило дворянское войско, а в крестьянскую рать вселило победную уверенность. В этот момент из засады по наступавшим шапсугам казаки открыли пушечный и ружейный огонь. Шапсуги смешались, наступление захлебнулось. Бжедуги выровняли строй и в две волны с казаками бросились на шапсугскую конницу. Шапсугов, еще минуту назад готовых праздновать победу, охватила паника. Очень скоро отступление превратилось в бегство. В страшном беспорядке шапсуги смяли пехоту союзных абадзехов. Напрасно крестьянские вожди пытались остановить своих бегущих воинов. Все было кончено. Предводители дворянского войска поздравляли еще живого Быты-Гирея с победой. «Теперь я умру спокойно», — так по легенде ответил знаменитый черкесский рыцарь.
