Казакам, доказавшим свою верность государыне, были возвращены их регалии: белое войсковое большое знамя, малые куренные знамена, булава кошевого атамана и перначи. Но главное, казаки получили гетмана, которым стал сам князь Потемкин. Оставалось получить только то, без чего невозможно самостоятельное, полнокровное существование любого казака, — землю.
В 1790 году, когда еще громыхали пушки войны с османами, Потемкин получил высочайшее позволение отвести черноморцам берег Черного моря между Днепром и Бугом с правом пользования «рыбными ловлями и всеми выгодами земли». Казаки не просто получали награду за доблестную службу, они обретали дом. Но совершенно неожиданно 5 октября 1791 года по дороге из Ясс в Николаев умирает заступник и покровитель черноморцев князь Потемкин-Таврический. Лишившись гетмана, казаки вновь превращаются в пасынков империи. Помещики, жадные до богатой земли Причерноморья, чинят всевозможные препятствия казачьей колонизации. Черноморцы вынуждены терпеть унижения и несправедливость. Ведь война закончилась, зачем нужны казаки? Любой неосторожный шаг мог привести к повторной ликвидации войска, а значит, и всех надежд на достойное будущее. Поэтому казачья старшина на все многочисленные жалобы отвечала так: «Собраться нам було трудно, а расточать нас чрез неповиновение — легко».
Вожаки казаков, недавно ведшие их в бой, теперь должны были найти способ получить землю, на которой они были бы хозяевами, а не гостями. Незадолго до смерти Потемкин лично даровал черноморцам Таманский полуостров, который отделен от Крыма Керченским проливом. Казачья старшина возложила свои надежды на получение этой земли. В 1792 году в Петербург отправляется депутация черноморцев во главе с Антоном Головатым. Выбор Головатого в руководители ответственной миссии был не случаен. Войсковой судья обладал всеми необходимыми знаниями и опытом. Он учился в Киево-Могилянской академии и бывал ранее в Петербурге. Четыре месяца Головатый добивался положительного решения главного в своей жизни дела. Известный историк кубанского казачества Федор Щербина писал, что Головатый «пустил в ход все: и знакомство с людьми сильными, и малорусскую песню, и чудачества казака-малоросса». Наконец, государыня императрица благосклонно отнеслась к прошению казаков и даровала им Тамань с правым берегом Кубани от устья до Усть-Лабинского редута. Как и прежде, от казаков правительство ожидало честной службы: «бдительно хранить пограничную линию от набегов закубанских горцев, соблюсти имя храбрых воинов и заслужить звание добрых и полезных граждан».