Воевать с горцами и защищать от них границы при таких условиях было делом в высшей степени трудным и рискованным. Горцы всегда могли натворить немало бед в плохо охраняемых местах, что и было в действительности. Нужно было или прибавить регулярных войск, или усилить казачьи кадры. Собственно, немногие станицы Кубанского полка продолжали еще заселяться. Донские казаки, поднявшие восстание из-за переселения их на Кубань, охотно, без всякого принуждения, шли на прикубанские земли, как только осели их предшественники по Кубанской границе. Были вольные и тайные переселения. Край был богат свободными землями и угодьями для посевов и скотоводства. Для людей, державшихся старой веры, не существовало никаких стеснений на новых местах, и казаки-староверы охотно шли к своим единоверцам на Кубань. Неспокойные головы, любившие военную жизнь и приключения и жаждавшие борьбы с горцами, также покидали Дон и уходили на Кубань. Шла родня к родне и одностаничники к одностаничникам. Но все это совершалось в малых размерах, слабыми колонизационными течениями. Для обеспечения Кавказской пограничной линии требовался более широкий приток поселенцев.
Особенно заинтересованы были в такой постановке колонизации лица, руководившие военными действиями на Кавказе. По самому скромному расчету, для заселения границы по Кубани на Старой Линии граф Гудович потребовал переселения с Дона на Кубань 3000 казачьих семей. Между тем поселена была только одна тысяча семей. Нужны были еще переселенцы. И навстречу этой нужде пошли казаки бывшего Екатеринославского войска. Донцов правительство силой гнало на Кубанскую линию, екатеринославцы пошли туда по своей охоте.
Бывшее Екатеринославское казачье вой-ско имеет свою историю. Оно возникло одновременно с Черноморским войском и под влиянием тех же причин, как это последнее. Казаки потребовались для войны с турками. В то время, когда Черноморское войско формировалось исключительно из бывших запорожских казаков, Екатеринославское войско составилось из всевозможной вольницы. В него вошли вольные искатели приключений – малороссийские казаки, беглые крестьяне, однодворцы, старообрядцы, мещане и вообще разные выходцы на юг России. Добровольцы эти в 1788 году, в начале войны с турками, соединены были с Бугским казачьим войском и все вместе получили название сначала Бугского, а потом Екатеринославского казачьего войска. Екатерино-славское войско выставляло десять полков, тысячного состава каждый, и насчитывало до 50 562 д. обоего пола населения.
Благодаря разнообразному составу и массе не казачьих элементов в рядах Екатеринославского войска почти не оказалось своей старшины. Не из кого было выбирать офицеров. Так как Екатеринославское вой-ско оказалось смежным с Донским, то оно подчинено было этому последнему и называлось Екатеринославским или Новодонским войском. Донские старшины, по назначению правительства, управляли екатеринославцами и, как с пасынками, не стеснялись с чуждым им казачеством. Появились поборы, утеснения, назначения на службу не в очередь и т.п. В течение 8 лет этого зависимого положения екатеринославцам показалось настолько тяжелым донское иго, что они начали ходатайствовать о возвращении их «в первобытное состояние». Казаками пожелали остаться только бывшие бугские запорожцы. Тогда Екатеринославское войско снова было подразделено на две части: на Бугское войско и на пришлые элементы, составившие Екатеринославское войско. Первые, бугские запорожцы, были оставлены, согласно их желанию, в казачьем звании, а вторые, собственно екатеринославцы, переведены на казенный оклад на правах однодворцев. За прежнюю военную службу им дана была только двухлетняя льгота от подушного оклада.
Но и среди обращенных в податное состояние екатеринославцев произошел раскол. Часть их, преимущественно те, которые входили в полк знаменитого Платова, участвовавший в делах под Измаилом, Килией, Аккерманом и пр., нашли, что им дали мало земли, и не захотели быть однодворцами. Начались новые хлопоты о возвращении в казачество. В это время заселялись Черномория и Старая Линия. Слухи об обилии земель и приволье в этих местах дошли и до екатеринославцев, и они твердо порешили переселиться на Кавказ в казаки. Во главе движения стал казак Козьма Рудов. По доверенности от общества, сначала он обратился в Сенат с прошением об обращении екатеринославцев в казаки, но Сенат не решился удовлетворить эту просьбу без Высочайшего соизволения. Тогда в августе 1800 года Рудов подал прошение на Высочайшее имя. Опираясь на то, что екатеринославцы несли во время турецкой войны «службу на собственном иждивении» и что при обращении их в однодворцев им дали мало земли, он просил переселить екатеринославцев, в количестве 3300 душ муж. пола, «на Кавказскую линию казаками». Екатеринославцы, говорилось в прошении, привыкли к военной службе и не пожелали записаться ни в купечество, ни в мещанство. Сенату поручено было удовлетворить просьбу екатеринославцев по выяснении обстоятельств дела.
С этой целью Сенат предварительно собрал сведения о просителях через Слободского украинского губернатора и об условиях поселения казаков на Кавказе через губернатора астраханского. Первый ответил условно, что переселить их можно столько, сколько окажется в излишке, за наделением всех однодворцев 15‑десятинным наделом. Второй, астраханский губернатор Повалишин, донес о запросе Сената астраханскому военному губернатору и инспектору Кавказской дивизии г.-л. Кноррингу. Генерал Кнорринг воспользовался удобным случаем. Давши краткий очерк об условиях заселения Кавказа от Кизляра до Усть-Лабы казаками Кизлярского, Терского и Гребенского войск и Моздокского, Волгского, Хоперского и Кубанского полков, располагавших 248 старшинами и 4246 казаками служилого состава, он признал, что от переселения на Кавказ казаков бывшего Екатеринославского войска «важные произойдут пользы для границы». Самым расположением новых станиц по Кубани, между Кавказской и Усть-Лабинской крепостями, можно было уже загородить черкесам проход в русские владения на протяжении 90 верст. Затем новоселы могли образовать целый казачий полк пятисотенного состава, и часть полка могла быть назначена в другие места для защиты границы. Мнение генерала Кнорринга имело решающее значение для екатеринославских казаков.
После того как Сенат собрал все справки о переселенцах и доклад его по этому предмету представлен был Государю, 16 октября 1801 года Александр I утвердил мнение Сената, и вопрос о переселении бывших казаков Екатеринославского войска на Старую Линию был решен в положительном смысле.
Желающих переселиться на Кавказскую кордонную линию из пяти сел Изюмского уезда – Сухаревки, Терской, Ямполовки, Краснянской и Дериловой – записалось 770 душ муж. пола, и из шести сел уезда Старобельского, Новоайдарского, Спеваковки, Бахмутовки, Райгородской, Староайдарской и Трехизбенской – 2530 д., а всего 3300 д. м. пола. Но когда Старобельский нижний земский суд «сочинил» свои списки переселенцев, то в них попали однодворцы из других селений и даже из другого, Змиевского, уезда. Таких добавочных селений оказалось 7 по Змиевскому уезду и 4 по уезду Изюмскому, с 479 душами м. п. в обоих. Права на переселение Слободскоукраинским губернским правлением были признаны лишь за 3300 д. м. п., из числа их приказано было выбрать надежных доверенных лиц для осмотра мест поселения на Старой Линии.
Доверенными были есаул Гречишкин и сотник Фарафонов «со многими стариками». Ими осмотрены были как весь подлежавший заселению район, так и места, предназначенные под станицы. Станицы должны были находиться на известном расстоянии друг от друга и непременно близ существовавших уже укреплений. Екатеринославцам указаны были 4 редута: Ладожский, Тифлиский, Казанский и Темишбекский, при которых предполагалось расположить станицы. Доверенные, со своей стороны, нашли места эти подходящими для этой цели. Оставалось только переселить население бывшего Екатеринославского войска, находившееся еще на старом местожительстве. Осмотр мест новоселами производился в апреле и мае месяцах, а в сентябре и октябре 1802 года, как донес об этом в Тифлис генерал Кнорринг, на Кавказскую линию прибыли бывшие екатеринославские казаки и основали при 4 редутах 4 станицы, без всякой помощи казны, на собственные средства.
Но выбор мест под станицы не обошелся без затруднений. Г.-м. Шеншин в рапорте 13 августа из Усть-Лабы сообщил Кноррингу, что место под станицу Тифлисскую, разрешенное им для заселения, согласно желанию переселенцев, внизу у берега Кубани, он считал неудобным и полагал бы расположить станицу выше и ближе к редуту, под защиту его. То же писал Кноррингу о расположении станицы Темишбекской полковник Дияков. Место, первоначально избранное для этой станицы, он нашел низким, сырым и нездоровым. В низинах и впадинах, при дожде и грязи, могли образоваться топи и лужи, грозившие людям «тяжкими болезнями». К тому же местоположение это неудобно было и с точки зрения охраны его от горцев, как удаленное от укреплений и требовавшее особого охранного отряда. Сообразно с такими указаниями Шеншина и Диякова и было изменено расположение станиц Тифлисской и Темишбекской.
Екатеринославские казаки переселились в количестве 3277 д. м. п. и были распределены по станицам следующим образом: в станице Ладожской осело 232 семьи, в Тифлисской – 181, в Казанской – 223 и в Темишбекской – 226 семей. Годных к службе оказалось 1106 человек, престарелых 586 и малолетних 1505. Четыре сотни полка были распределены каждая в особой станице, а пятая сотня в станицах Казанской и Темишбекской. При организации из них Кавказского полка в состав администрации его вошли 4 лица из старшин бывшего Екатеринославского войска, 4 из Хоперского полка и 1 из Волгского. Военная коллегия предписала генералу Шеншину выбрать из трех кандидатов одного войскового старшину и других недостающих в полку чинов. Старинные казачьи порядки, хотя и в измененном уже виде, были применены к новому казачьему полку. Инспектор Кавказской кавалерии г.-л. Шепелев рапортом 12 августа донес командующему войсками в Грузии князю Цицианову, что, согласно указу Государственной военной коллегии от 11 июня 1803 года об образовании Кавказского, по образцу Кубанского, полка, он поручил г.-м. Шеншину произвести в его присутствии выборы офицеров. Казачий обычай выбора офицеров был осуществлен под надзором генерала.