Спустя четыре года, в августе 1787-го, Потёмкин повелел старшинам бывшего Запорожского войска Сидору Белому и Антону Головатому собрать волонтерские команды из казаков, которые раньше служили в Сечи. Сначала эти подразделения назвали Войском верных казаков — в отличие от «неверных», которые осели на территории Османской империи. Но уже в декабре 1788-го их переименовали в Черноморское казачье войско.

 
В июне 1792 года Екатерина Великая подписала указ о переселении Черноморского казачьего войска на правобережные земли Кубани. Тогда же она составила жалованную грамоту, согласно которой эти земли переходили казакам в вечное владение «со всеми угодьями, к ним принадлежащими, с представлением войсковому начальству внутренней расправы и обывателям свободной внутренней торговли». Кроме того, в собственность войска перешел Таманский полуостров вместе с рыболовными угодьями. Всего казакам с этого времени принадлежало около 33 тысяч квадратных километров земли между Азовским и Черным морями, реками Кубанью и Еей. Взамен от войска требовалось «бдение и стража пограничная от набегов народов закубанских».

 
30 июня 1792 года императрица принимала в Царском Селе делегацию черноморских казаков, которую возглавлял войсковой судья Антон Головатый. По старинной русской традиции гостям императорского дворца поднесли хлеб и соль на позолоченном серебряном блюде, которое затем подарили казачьему войску. Екатерина передала черноморцам грамоту о пожаловании земель, а также распорядилась вручить войсковые награды: серебряные литавры, наградные Георгиевские трубы, которые в то время служили символом воинской доблести, и знамя «За веру и верность».

 
Грамота не только определяла границы обитания казаков на Кубани, но и давала новое имя их главному поселению, которое называлось тогда Карасунский кут. С 1793 года по указу императрицы его переименовали в Екатеринодар.