По окончании военных действий Черноморское войско было поселено на землях между Бугом и Днестром. Положение казаков на новых землях было неопределенным. Чиновники, землевладельцы, недовольные бегством на земли войска крестьян, не желали такого соседства. Казачья старшина решила обратиться к правительству с просьбой о переселении войска на Тамань и близлежащие земли. Депутация во главе с А. Головатым отправилась в столицу весной 1792 г., а уже 30 июня того же года Екатерина II подписала Жалованную грамоту, по которой черноморским казакам в вечное пользование передавалась правобережная Кубань от устья до Усть-Лабинского редута, а также Фанагория.
Переселялись черноморские казаки в 1792–1793 гг. несколькими партиями под руководством С. Белого, К. Кордовского, 3. Чепеги, А. Головатого. Всего переселилось на Кубань около 17 тысяч человек, но уже к 1795 г. численность войска приближалась к 25 тысячам человек. В 1793–1794 гг. казаками-черноморцами были основаны 40 куренных селений (38 сохранили названия куреней Запорожской Сечи, а также были добавлены Березанский и Екатерининский), заложен войсковой град Екатеринодар — административный центр Черномории.
Однако численность казаков-черноморцев была явно недостаточной для освоения более 3 млн десятин пожалованных земель, к тому же трудности на месте (климат, болезни, схватки с горцами) приводили к людским потерям. Крестьяне бежали на Кубань «за волей», однако существенно повлиять на численность населения Черномории не могли. Правительство трижды организовывало переселение малороссийских казаков и крестьян в Черноморию из Полтавской, Черниговской и Харьковской губерний — в 1809–1801, 1821–1825 и 1845–1849 гг. В результате численность населения увеличилась более чем в 7 раз и составила около 180 тысяч человек.
Параллельно с переселением черноморцев правительство планировало колонизацию земель от крепости Усть-Лабинской до верховий реки Кубани. Сюда планировалось переселить 3000 семей донских казаков, служивших в это время на Кавказской линии. Донцы в ответ взбунтовались и бежали на Дон. Однако вскоре волнения были подавлены, и в 1794 г. переселение началось.
Станицы Темнолесскую, Воровсколвескую, Прочноокопскую, Григориполисскую, Усть-Лабинскую основали казаки Дона, которые составили Кубанский полк. К середине XIX в. население Кубанской линии составляло более 300 тысяч человек, в том числе 122 тысячи — проживающих на Кубани. В административном плане Черномория составляла отдельную административно-территориальную единицу — «Землю Черноморского войска», подчиненную таврическому губернатору. Местное управление определялось «Учреждением об управлении губерний» и Жалованной грамотой Екатерины II от 30 июля 1792 г., а также составленным войсковой старшиной документом — «Порядком общей пользы» (1794), закреплявшим ведущее положение казачьей «аристократии» во всех отраслях жизнедеятельности войска. Высшая местная власть сосредоточивалась в руках войскового правительства, во главе которого стояли атаман, судья и войсковой писарь. Черномория делилась на пять округов: Екатеринодарский, Фанагорийский, Бейсугский, Ейский, Григорьевский. Управление в округах осуществляли окружные правления, наделенные полицейскими функциями.
В 1796 г. Черномория вошла в состав Ростовского уезда Новороссийской губернии, войсковое правительство преобразовалось в войсковую канцелярию с правами губернского правления. С 1802 г. по военной части войско подчинялось Военной коллегии, по гражданской — Сенату. В силу военной необходимости в 1820 г. Черномория была подчинена начальнику Отдельного Кавказского корпуса А. П. Ермолову с присоединением к Кавказской губернии (с 1827 г. — Кавказской области). В 1842 г. было утверждено «Положение о Черноморском войске», в соответствии с которым Черномория по военной и гражданской части подчинялась Департаменту военных поселений, непосредственно на Кавказе — командиру Отдельного Кавказского корпуса. В административном отношении Черномория делилась на три округа — Таманский, Екатеринодарский и Ейский с окружными правлениями.
Казаки Кавказской Линии первоначально не имели единого устройства. По мере переселения на Кубань донских, малороссийских казаков, жителей казенных селений, нижних чинов Кавказской армии (Тенгинского, Навагинского пехотных полков) из них формировались отдельные полки с полковыми правлениями (Кавказский, Хоперский, Ставропольский), которые в 1832 г. вошли в состав Кавказского Линейного казачьего войска (положение о войске было принято только в 1845 г.).
Основной для казаков была служба на месте проживания — «бдение и стража пограничная от народов закубанских». В дореформенный период служба казачества была поголовной и практически пожизненной. В обмен на земельный надел и некоторые льготы (освобождение от рекрутских наборов, земских денежных платежей, право беспошлинной торговли в войске, рыбной ловли с уплатой пошлины в войсковой капитал, довольствия солью из войсковых запасов) казаки расплачивались длительной и тяжелой службой.
