1492 року, коли Христофор Колумб висадився на одному з островів Карибського моря і назвав його Сан-Сальвадор, а король Фердинанд та королева Ізабелла підписали указ про вигнання євреїв з Іспанії, козаки вперше з’явилися на міжнародній арені. Згідно зі скаргою, відправленою цього року кримським ханом до великого князя литовського Олександра, його піддані з Києва та Черкас захопили та пограбували татарський корабель, що, схоже, перебував у пониззі Дністра. Князь ніколи не піддавав сумніву, що це могли бути його люди, або що вони, можливо, займаються розбоєм у степах. Він наказав своїм прикордонним («українним») урядовцям провести розслідування щодо козаків, які могли брати участь у цьому набігу. Також він звелів стратити винних, а їхнє майно, де, імовірно, були й вкрадені товари, віддати представникам хана.
Якщо наказ Олександра й був виконаний, він не мав тривалого ефекту. Наступного року кримський хан звинуватив козаків із Черкас у нападі на московського посла. 1499 року козаки були помічені в гирлі Дніпра, де спустошували околиці татарської фортеці Очакова. Щоб припинити козацькі походи до Чорного моря вниз по Дніпру, хан планував заблокувати річку ланцюгами в районі Очакова. Здається, цей план так і не був втілений або не мав жодного впливу на діяльність козаків. Від скарг хана до великого князя також було мало користі.
Намагаючись припинити козацькі набіги, литовські прикордонні старости водночас використовували козаків для захисту кордонів від татар. 1553 року великий князь відправив черкаського та канівського старосту Дмитра Вишневецького за дніпровські пороги для будівництва невеликої фортеці, що мала б зупинити козацькі походи вниз по Дніпру. Вишневецький використав для цього завдання підлеглих йому козаків. Не дивно, що кримський хан побачив у козацькій фортеці на острові Мала Хортиця зазіхання на його володіння і за чотири роки відправив військо, щоб вигнати Вишневецького з його «січі». У народній традиції Вишневецький запам’ятався як перший козацький гетьман (титул, який польська армія надавала своїм верховним командувачам) і безстрашний борець проти татар і турків.
На середину XVI століття землі на південь від Києва були вже заповнені козацькими поселеннями. «А Київська земля — щаслива, процвітаюча й багата населенням, бо на берегах Борисфена та інших річок, що впадають у нього, багато густонаселених міст і сіл», — пише Михалон Литвин. Він також пояснює походження поселенців: «Деякі ховаються від батьківської влади, або від неволі, або від служби, або від [покарання за] злочини, або від боргів чи ще чогось іншого; інших приваблює [до цього краю] багата дичина та родючі місця. І, спробувавши щастя в цих фортецях, вони ніколи звідти не повертаються». Судячи з опису Михалона, козаки доповнювали свої доходи від полювання та риболовлі елементарним розбоєм. Він писав, що в деяких брудних та бідних козацьких хатах було «повно дорогих шовків, коштовного каміння, соболів та іншого хутра і прянощів». Там він знаходив «шовк дешевший, ніж у Вільні, і перець дешевший за сіль». Купці перевозили степами ці ласощі та предмети розкоші з Османської імперії до Московського царства або Королівства Польського.
Хоча перші козаки були міськими мешканцями й жили вздовж Прип’яті та Дніпра, на кінець XVI століття їхні лави збільшувалися за рахунок місцевих селян. Цей наплив поклав край політичній, етнічній та релігійній невизначеності козаків — європейські автори тих часів гадали, чи були вони кримськими татарами та ногайцями, чи українськими підданими князів і королів, чи сумішшю всіх народів і релігій. Абсолютну більшість козаків тепер становили українці, котрі прибули з величезних маєтків (або латифундій) магнатів і шляхти, аби уникнути того, що історики називають «другим виданням кріпацтва». Як уже зазначалося в попередньому розділі, магнати й шляхта намагалися залучити нових поселенців до своїх новопридбаних володінь на українському прикордонні, що були небезпечні для життя через постійну загрозу татарських нападів, обіцяючи їм звільнення від податків на певний період часу. Щойно цей період завершувався, багато селян рухалися далі, у небезпечний степ, щоб уникнути оподаткування. Чимало з них приєднувалися до козаків і радикалізували їхню суспільну політику під час повстань.