Перша згадка про козаків відноситься до кінця XIII ст., — «Словник половецької мови» називав так сторожа або вартового. У 1308 р. згадується про присутність козаків у Криму — місті Сугдея (Судак), щоправда, вже в значенні «розбійників». До кінця XV ст. словом «козак» у русичів і татар продовжували позначатися озброєний конвоїр або розбійник.
Перша згадка про козаків в міжнародному листуванні датується кінцем XV ст. У 1492 р. кримський хан Менглі-Гірей скаржився великому литовському князеві Олександру, що його купці були пограбовані на Нижньому Дніпрі, і той пообіцяв з’ясувати це питання «серед козаків». Саме тоді починає формуватися козацтво як новий стан; до попередніх його визначень додається ще одне — вільна, незалежна людина. Правителі Польщі і Литви швидко зрозуміли, що вигідніше не воювати з козаками, а привернути таке активне і енергійне військо на службу державі. Польські королі почали використовувати загони козаків для охорони південних меж від набігів татар.
До останньої чверті XVI ст. козацтво залишалося швидше родом занять, ніж соціальним статусом. Часто адміністрація південних околиць Польщі і Литви та представники шляхти брали оборону земель в свої руки — саме їх і називають першими гетьманами. При цьому вони використовували козацькі наймані дружини, які за свій кошт озброювали, забезпечували кіньми і зброєю. Таким чином, козаки ставали сюзеренами груп васалів, які платили їм відданістю і службою. Серед перших козацьких ватажків були київський воєвода Семен Полозович, черкаський і канівський староста Євстафій Дашкевич, Бернард Претвіч, Хмельницький староста Предслав Лянцкоронський і багато інших.
У 1508 р. Семен Полозович вперше розбив татар, а в 1520-х роках він з чорнобильським намісником Кмітічем близько тижня захищав переправу на Дніпрі, не пропускаючи татар.
У 1516 р. Хмельницький староста Предслав Лянцкоронський здійснив похід на Очаків і, як колись лицарі-хрестоносці, дійшов до Єрусалиму і мусульманських країн, де навчався військовому мистецтву.
Разом з ним в 1516 р. і 1528 р. ходив і Євстафій Дашкевич, який здійснював і самостійні, не менш успішні походи на татар. У 1523 р. він узяв штурмом і спалив Очаків. Коли в 1533 р. канівського і черкаського старосту (1514-1535 рр.) Дашкевича на польському сеймі запитали про те, як боротися з набігами татар, він запропонував у місцях розташування їх переправ на Дніпрі і на найближчих до них островах спорудити фортеці, а гарнізони вкомплектувати з козаків. Але польський уряд, хоч і схвалив проект Дашкевича, не виділив коштів. Тоді він почав організовувати експедиції проти татар на власні гроші. Євстафій Іванович користувався повагою і в стані ворогів — не раз був провідником татарських загонів у московські землі. Так, в 1521 р. він ходив на Москву і Казань разом з Менглі-Герєєм. Легенди розповідають, що Дашкевич і зовні не відрізнявся від татар, знав їх мову і звичаї, часто ходив у їх тил і залишався невпізнанним. У долі цієї легендарної людини, як в дзеркалі, відбилася вся сутність складних і суперечливих взаємин українсько-татарського прикордоння XVI ст.
У 1540 р. старостою фортеці Панів став Бернард Претвіч — німець за походженням, шляхтич із Сілезії, який більше 20 років патрулював подільські кордони. Він то здійснював набіги на татар для звільнення полонених, то влаштовував каральні експедиції на Килію, Акерман (сучасний Білгород-Дністровський), Очаків і навіть до Криму. Сучасники говорили, що поки був живий Претвіч, татарські дороги заросли травою і вороги забули дорогу до України. Він вступав у бій з ворогами більше 70 разів і жодного разу не програвав. Але козацьким гетьманом Претвіч себе не вважав, хоч і очолював їх в багатьох битвах і походах. На те були вагомі політичні причини: у 1540-х роках відношення між імперією Османа і Польщею погіршали, не в останню чергу через постійні козацькі набіги. Поляки лукавили, кажучи, що не знають, хто організовує такі вилазки. Багато шляхтичів і навіть магнати «спонсорували», а іноді і безпосередньо керували козацькими походами.
Більшість істориків дотримуються думки, що першим козацьким гетьманом в повному значенні цього слова був виходець із знатної сім’ї, спадкоємець роду Гедиміновичів князь Дмитро Корибут-Вишневецький. В історію він увійшов як «Байда» і став втіленням образу князя-козака, прообразом якого можна вважати князя X ст. Святослава Ігоревича. Саме про Вишневецького складена знаменита «Дума про Байду», в якій князь наділений легендарними рисами.
У XVI ст. ситуація в українських землях складалася так, що козаками ставали не тільки представники народу, але й православна шляхта, якій складно було зробити кар’єру в державі, де головні ролі віддавалися католикам. Предком Байди був князь Корибут-Дмитро, син Ольгерда Гедиміновича, великого князя литовського. Правнук Корибута-Дмитра, Солтан, побудував замок Вишневець на Тернопільщині і першим почав називати себе Корибутом-Вишневецьким. Дмитро був його правнуком. Матір’ю Дмитра була Анастасія Олізар, предками якої були албанські і сербські князі Скандерберги і Якимі, а також молдавські господарі Деспоти. В кінці 30-х років XVI ст. Вишневецький брав участь у походах Претвіча, а в 1540-х роках султан Сулейман II скаржився королеві Сигізмунду Августу, що козаки «Дмитрашки» з червня 1548 р. по грудень 1549 р. постійно турбували турецьку фортецю Очаків. За успішну кампанію в 1550 р. Вишневецький отримав від короля не дуже спокійну посаду старости черкаського і канівського. Але і князь не відрізнявся меланхолійністю: він не просто захищав південні кордони, але використовував наступальну тактику, переслідуючи татар на їх же території.
Мудрий політик, Вишневецький із загоном прибув восени 1553 р. до Стамбулу для врегулювання прикордонних конфліктів безпосередньо з султаном Сулейманом II (1495-1566 рр.). Невідомо, як проходили переговори, але гетьман виїхав з турецької столиці з почестями і подарунками від султана.
Польський король Сигізмунд Август подарував Вишневецькому титул «стражника Хортиці». У 1556 р. починається будівництво укріплень на острові Хортиця (достеменно не відомо, була це Мала або Велика Хортиця) і на сусідньому острівці Токмаковка, розташованих біля сучасного Запоріжжя. Місце розміщення укріплень було вибрано тактично грамотно — звідси князь міг контролювати пересування кримських татар. Фортеця Вишневецького стала першою запорізькою Січчю, що займала вершину скелястого острова, який підносився на 15 м над Дніпром, так що висадка ворогів не могла залишитися непоміченою. Щоправда, археологічні дослідження 1968 р. на Малій Хортиці не виявили слідів укріплень козацьких часів, тому питання про те, де знаходилася Січ — на Малій або Великій Хортиці, залишається відкритим.
24-денна облога острова татарами була безрезультатною. Вороги зважилися на облогу після того, як козаки спалили їх форпост Іслам-Кермен і передмістя Очакова. Осінню 1557 р. хан знову обклав Січ, Вишневецькому довелося відступити до Черкас, а його фортеця була зруйнована.
Дмитро Вишневецький був авантюристом. У кінці 1556 р., побачивши, що король не проти помиритися з султаном, він вирішив поступити на службу до Івана Грозного і після зруйнування Січі відправився до Москви. Цар подарував князеві містечко Бельов з волостю і грошову винагороду. На той час між Литвою і Московією почалася Лівонська війна (1558-1583 рр.), і князь, не бажаючи остаточно розривати відносин зі своєю батьківщиною, уникав участі в бойових операціях в Лівонії. Весною 1559 р. за завданням Івана Грозного Вишневецький на чолі 30-тисячного війська з’явився на Доні, щоб через Азов увірватися до Криму, і навіть підійшов до Перекопу. Але цар, «перемкнувшись» на війну в Лівонії, фактично залишив Вишневецького наодинці з ворогом, і тому довелося повернутися до України.
У 1562 р. почалося будівництво нових укріплень на Монастирському острові, але доля підготувала Вишневецкому несподіваний поворот. На сеймі він познайомився з магнатом-авантюристом Ольбрехтом Лаоським, який переконав Байду поборотися за молдавський престол, — адже в роду Вишневецького були і молдавські правителі. По дорозі до Молдови союзники посварилися, і Лаоський із загоном повернувся до Польщі, а Вишневенький недалеко від річки Серет потрапив у пастку. При князеві було всього 500 козаків, тому молдавський правитель Штефан — ставленик султана, зміг оточити запорожців. Вишневенький був захоплений у полон за дивних обставин — його знайшли в копиці сіна молдавські селяни. Очевидно, він був важко хворий, говорили, що це було отруєння, «нитки» якого тягнулися до Москви. Молдавський господар видав Байду султанові Сулейману II, і в 1563 р. князя було страчено. Як свідчить «Дума про Байду», князь відмовився приймати іслам і був повішений за ребро на крюк, вбитий у міську стіну. Байда вмирав три дні, нещадно лаючи при цьому султана. За наказом останнього, князя застрелив один з турецьких стрільців. Так закінчив своє життя Дмитро Корибут-Вишневецький, чи то справжній український патріот і захисник українських земель, чи то литовський і московський найманець і авантюрист. На згадку про нього в старовинному українському лексиконі збереглося слово «байдувати», що означало те ж, що й «козакувати», — вести вольне, незалежне життя.
Після смерті Вишневецького в 1570 р. уряд нарешті усвідомив необхідність фінансування козацтва. В цей час був набраний найманий козацький загін з 300 чоловік, на чолі якого стояв панський шляхтич Ян Бадовський. Тоді ж зробив походи в степ ще один легендарний гетьман — князь Богдан Ружинський. У 1575 р. він з козаками вночі захопив укріплення Ор на Перекопі, потім — Кафу, визволивши сотні невільників. У 1576 р. Ружинський атакував турецьку фортецю Аслам-Керман на Нижньому Дніпрі, де і загинув під час невдалого вибуху міни, закладеної козаками під кріпосну стіну.
У травні 1576 р. польським королем був вибраний семиградський князь Іштван Баторі, більш відомий як Стефан Баторій. Він, як досвідчений воїн, провів реформу польського війська. У липні 1578 р. у Львові був підписаний договір з козацькими представниками - «Ухвали з низовиками», за якими на королівську службу з платнею і утриманням бралося Дніпровське військо у складі 500 козаків, імена яких були внесені до списку-реєстру. Гетьманом був призначений черкаський староста князь Михайло Вишневецький (двоюрідний брат славного «Байди»), «старшим» — брацлавський шляхтич Ян Орішовський, а писарем й інтендантом — Янчі Бегер, вірний служник Стефана Баторія. Столицею козакам було призначено місто Трахтемирів під Каневом. Там розміщувався козацький шпиталь і зберігалися регалії, які були даровані королем, — корогва, військова печатка, бунчук, булава, бубна і труби. У свою чергу, «реєстрові» козаки не повинні були воювати у Валахії, розбишакувати, нападати на Очаків, шкодити кримському ханові. Поступово кількість козаків на службі польської корони зросла, вони отримали численні вільності і підкорялися лише місцевій адміністрації. Це був перший крок на шляху становлення Війська Запорізького.
