На кілька років пізніше, після численних скарг кримського хана на напади козаків, ситуація змінилась для козацтва на краще. Сигізмунд І, який на ремствування хана відповідав, що напади на татарські володіння викликані агресією проти українських земель князівства Литовського, ясно відчував, що загроза масштабної кампанії збоку татар проти Литви й Польщі стає все більш реальною. Вже у 1541 році, як свідчать документи тієї епохи, від Сигізмунда І в Подніпров'я прибув урядовець, якому було доручено створити реєстр козаків київських, черкаських і канівських, доручивши їх посиленому контролю з боку старост. Припускаємо все ж, що такий крок Сигізмунда І більше був спрямований на утримання козацтва від бойових дій проти татар, аніж на їх заохочення. Але наступник Сигізмунда І, король Сигізмунд II Август, вирішив дещо змінити попередній план свого батька — він не намагався перешкоджати діяльності козаків, натомість залучаючи їх на королівську службу. За дорученням короля коронний гетьман вербував загони козацтва саме для таких цілей, для яких колись хотів їх комплектувати Євстафій Дашкевич. Ці козаки отримували особливий статус. Вони не підкорялись владі старост, а безпосередньо перебували під владою призначеного сеймом «старшого й судді усіх низових козаків». Спочатку в козацькому загоні, котрий і став пізніше основою для реєстрового козацького війська, нараховувалось усього 300 козаків, і завданням, яке перед ними ставила влада, було стримування від свавільства решти козацтва. Але, як зазначає М. Грушевський, це були далеко не всі наявні козацькі сили, а з огляду на те, що влада змушена була надати козакам, записаним до реєстру, особливий статус, логічно припустити, що особливу юрисдикцію й підпорядкування спеціальному козацькому суду отримали й решта козаків Придніпров'я. Таким чином, пише Грушевський, це найперше козацьке військо, хоч і не виконало своєї функції по придушенню козацького свавілля, але воно зіграло немалу роль у формуванні козаччини в майбутньому.
Так коротко можна описати появу козацтва на теренах України. Отже, ми бачимо, що до часу, коли в пониззі Дніпра з'явився князь Дмитро Вишневецький, процес створення нового суспільного класу під назвою козацтво, було майже завершено. Майбутньому козацькому гетьману залишилось лише закінчити формування військових підрозділів і заявити про себе на теренах Речі Посполитої, Московського князівства, Оттоманської Порти і Кримського ханства. Однак розцінювати Вишневецького як першого козацького ватажка було б помилкою. Дещо раніше, на початку XVI століття, на історичній арені з'явились Євстафій Дашкевич, що його ми вже згадували раніше, а також Предслав Ляндскоронський. Доля обох воєвод так чи інакше була пов'язана з козаччиною, тому у деяких джерелах саме їх іменують першими козацькими гетьманами. Але, хоча відомо, що Дашкевич і Ляндскоронський, перебуваючи на чолі прикордонних староств, неодноразово організовували козацькі походи проти татар, їх навряд чи можна вважати гетьманами козацтва. Скоріше людьми, котрі на певному етапі своєї діяльності зверталися за допомогою до козаків, одночасно залишаючись королівськими службовцями. Все ж коротко зупинимось на цих особистостях.
Євстафій Дашкевич, троюрідний небіж Яна Ходкевича, одного з представників магнатства Великого князівства Литовського, народився на Житомирщині 1472 року. Відомо, що на початку XVI століття Дашкевич перебував на службі у московського Великого князя Івана III. Саме під час цієї служби Дашкевич брав участь у повстанні Михайла Глинського 1508 року. Суть повстання полягала в тому, що Глинський, підтримуваний Московським князівством, мав намір відділити від Литви Україну та Білорусь. Після поразки повстанців у битві під Гомелем князь Глинський змушений був тікати до Москви, де й отримав від князя боярство, а разом з ним великі земельні маєтності. Дашкевичу ж не залишалося нічого іншого, як повернутися в Україну і поступити на службу до князя литовського. Вірогідно, Дашкевича за участь у повстанні не було покарано, позаяк дуже скоро ми бачимо його на посаді старости канівського, а вже з 1514 року він призначений і черкаським старостою.
Оборона південних кордонів Литовської держави від нападів кримських татар вимагала від старости багато зусиль, оскільки, як вже говорилося, великий князь не надто переймався наданням допомоги прикордонним старостам. Напевне, саме тому Дашкевич почав залучати до військових експедицій козаків. Уперше про це згадується на початку XVI століття. Дійшовши згоди з козацтвом, Дашкевич спільно з козаками організував два походи на землі Московського князівства. Перший з цих походів відбувся 1515 року і був спрямований на Сіверщину, а другий, 1521 року, — на Москву.
Відомо, що під час тих походів землі від Воронежа до Москви сильно постраждали від дій козаків і кримських татар, котрі теж приймали участь в походах. Після 1521 року, повідомляють історичні джерела, Євстафій Дашкевич попав у татарську неволю, але перебував там зовсім недовго. Вже у 1523 році він на чолі українських козаків вперше напав на Очаків і зруйнував його. Звідтам козаки на чолі з Дашкевичем пішли у Крим і спустошили там Ґізлев, Карасубазар і Ак — Мечеть. Продовжувалась співпраця старости з козаками й надалі. Так, у 1528 році разом з Предславом Лянцкоронським і великим загоном козаків він знову атакував Очаків і там тричі розгромив татарські загони. У 1531 році саме під командуванням Євстафія Дашкевича козаки відбили напад на Черкаси, здійснений кримським ханом Саадат — Гіреєм. Неодноразово приймав Євстафій Дашкевич участь у битвах з татарами і після того, здобувши авторитет у козацькому середовищі. Помер він у 1536 році, залишивши по собі пам'ять оборонця кордонів України. Образ Дашкевича ми бачимо на відомій роботі видатного польського художника Яна Матейка. Створений уявою автора XIX століття, Дашкевич дивиться на нас крізь віки розумними ясними очима з — під високого чола й хутряної козацької шапки. Зодягнений у кольчугу і жупан, з мушкетом у руках, стародавній прикордонний староста чатує на ворога.
Рік народження іншого представника литовського прикордонного воїнства XVI століття, Предслава Ляндскоронського, невідомий. Однак з огляду на те, що він приймав участь у походах спільно з Євстафієм Дашкевичем, можемо припустити, що Лянцкоронський народився на початку останньої чверті XV століття. На історичній арені він з'явився 1506 року. Даних про його діяльність збереглось не надто багато. Але і цього достатньо, щоб підтвердити приналежність Лянцкоронського до одного з найвпливовіших українських можновладних родів. Батько його був сенатором сейму. Одружившись на доньці Костянтина Острозького, Лянцкоронський пов'язав себе родинними стосунками з сім'єю найвідомішого українського просвітителя свого часу. Крім того, він став свояком великого князя литовського Олександра І, що теж забезпечувало йому значний вплив у суспільстві. Визнання його як полководця прийшло до Предслава Лянцкоронського в 1512 році, під час війни Великого князівства Литовського з Кримським ханством. Будучи на посаді кам'янецького старости, Лянцкоронський зібрав під свої штандарти, окрім жовнірів і шляхти, значну кількість козаків. Разом з князем Костянтином Острозьким він став на чолі українсько — польського війська, яке завдало нищівної поразки кримській орді. Цей похід приніс йому таке визнання, що, як пише Д. Яворницький, у Польщі та Литві Предслава Лянцкоронського почали шанувати як найліпшого полководця свого часу, «який багато подорожував різними країнами Європи та Азії, вивчив усі бойові прийоми кращих європейських та азіатських полководців». В майбутньому цю славу йому ще не раз вдавалося підтвердити новими блискучими перемогами.
Відомо, що 1516 року, в черговий раз об'єднавши під своєю командою великий загін козаків, Лянцкоронський форсував Дністер і попрямував на південь. Козаки сміливо проникли на територію, контрольовану турками, і в передмістях Акерману (нині місто Білгород — Дністровський Одеської області) вщент розбили з'єднані турецько — татарські війська, що спробували відстояти місто. І хоч до штурму самої фортеці Лянцкоронський не вдавався, козаки надовго залишили по собі згадки в Бессарабїї. Вони захопили чимало трофеїв, полонених, великі табуни коней, череди рогатої худоби та овець. Зайве казати, що турки, які звикли вважати себе повновладними господарями Акерману, були вкрай розлючені таким вчинком козаків. Швидкими темпами було зібране військо, котре мало на меті наздогнати козаків, помотатися за поразку і повернути награбоване. Наздогнати Лянцкоронського туркам вдалося біля озера Овидів, що знаходиться поблизу Очакова. Переобтяженому здобиччю козацькому загону важко було протистояти турецькій і татарській кінноті. За логікою, козаки мали б покинути всі трофеї і рятуватися відходом. Саме на це й розраховували турецькі й татарські командири. Але вони помилилися у своїх розрахунках. Лянцкоронський захистив свої сотні рухомим табором з возів і зустрів ворога мушкетним та артилерійським вогнем з — поза укріплень імпровізованої фортеці. Така тактика бою, здавна відома козакам, давала їм можливість, як стверджує Д. Яворницький, витримувати напади війська, котре вдесятеро переважало у кількості. За кілька днів напруженого бою козаки одержали чергову перемогу. Тож як не прикро було турецьким і татарським воєначальникам повертатися ні з чим, вони мусили дати козакам піти зі своїх земель переможцями.