В 1469 году многочисленное татарское войско, составившееся за Волгой из беглецов, разбойников и изгнанников и назвавшееся казаками, по словам польского историка Длугоша, прошло от Волги за Днепр и опустошило Подолию. В 1492 году, при князе Иване III и крымском хане Менгли-Гирее, стали известны ордынские казаки. В 1601 году Иван III жаловался турецкому султану на азовских казаков, от которых сильно страдали наши послы и купцы. Несколько позже этого сын Ивана III, Василий Иванович, требовал от султана, чтобы он запретил азовским и белогородским казакам подавать помощь Литве, воевавшей с Москвой; в то же время, когда русский посол Коробов, бывший в Азове, потребовал себе провожатых для проезда через степи, то ему отвечали, что в провожатые, за отсутствием азовских казаков, ему некого дать. В 1510 году известны были казаки в Белогороде, или Аккермане, Перекопе и Крыму. В Крыму все татары этого времени разделялись на три сословия: углан, или улан, князей и казаков; улане принадлежали к верхнему сословию; князья – к среднему, владевшему поземельной собственностью, но зато постоянно воевавшему и от этого получавшему добычу; казаки – к низшему сословию. Крымский хан Менгли-Гирей, заключая договор с русским царем Иваном Васильевичем Грозным, обещал не дозволять воевать "ни уланам, ни князьям, ни казакам". В этом же 1510 году великий князь литовский Сигизмунд II жаловался крымскому хану на перекопских казаков, нападавших на литовские области. В 1516 году крымский хан Мухаммед-Гирей писал Сигизмунду II, что происшедшее нападение татар на Украину сделано было белогородскими казаками. В 1550 году литовский писатель Михалон Литвин между разными татарскими ордами упоминает и о казацкой орде.
В 1561 году перекопский царь писал польскому королю Сигизмунду-Августу о желании 24 белогородских татарских казаков "оказать службу литовскому государю идти на землю московскую"; приложенные при письме перекопского царя имена белогородских казаков все восточного происхождения, каковы: Аглаберды, Аличембей, Акмалла-ага, Бакай-ага, Бассан-али, Джарлы-ага, Чабан-ага и другие.
Вслед за известием о татарских казаках находим известие и о южнорусских. По мнению Максимовича, исторически известными становятся на Украине казаки уже с 1471 года, когда Киевское княжество обращено было в воеводство. По известию летописца XVII века Мартина Бельского, в 1489 году, во время преследования татар, ворвавшихся в Подолию, сыном короля Казимира IV, Яном Альбрехтом, впереди литовского войска шли до притока Буга, Саврана, казаки, хорошо знавшие местность Побужья. По указанию Антоновича, именем казаков, в 1491 году, назвались крестьяне в Червонной Руси, восставшие на защиту своих прав. Но документальное свидетельство о существовании украинских казаков в первый раз встречается в 1499 году в уставной грамоте великого князя Литовского Александра о воеводских доходах, данной киевскому войту и мещанам: "Который казаки з верху Днепра и с инших сторон ходят водою на низ, до Черкас и далей, а што там здобудуть, с того со всего воеводе десятое (десятую долю) мають давати; а коли рыбы привозят з верху, або з низу, просолныи(ой) и вялыи(ой) до места киевского, тоди мает осичник воеводин то осмотрети и обмитити (пометить) и мает на город взяти от бочки рыб по шести грошей, а от вялых рыб и свежих десятое (десятую штуку). А коли привезут до места киевского рыбу свежую, осетры, тогды не мают их целиком продавати, оли-ж (но) мусить осинник от каждого осетра по хребтине взяти, а любо (либо) от десяти осетров десятого осетра". В 1503 году, по свидетельству Архива Юго-Западной России, становятся известными черкасские казаки и казаки князя Дмитрия. Те и другие составляли уже иррегулярное войско в Литве; они организованы были по мысли правительства для защиты границ Литвы от набегов татар и состояли в ведении так называемых старост, то есть управителей областей, городов и замков государства. Такие казаки набирались самими старостами и нередко прозывались именами или фамилиями самих же старост: казаки князя Дмитрия, казаки князя Ружинского, казаки Мировицкого. В это же время становятся известными особые роты, или военные отряды в казачьем быту: так, под 1503 годом польский хронист Пясецкий упоминает о Щуровой казачьей роте в городе Черкассах. В 1508 году одна часть казаков, под начальством брацлавского и виленского старосты, князя Константина Ивановича Острожского, разгромила наголову загон татар, грабивших пограничные области Литовской Руси; другая часть казаков, под начальством "славного казака Полюса-русака", разбила другой загон татар. В 1512 году казаки, вместе с поляками и украинскими насельниками, участвовали в погоне за татарской ордой, ворвавшейся в южные пределы Литовского великого княжества. Начальниками над казаками и поляками были князь Константин Иванович Острожский и каменецкий староста Предслав Ландскоронский.
Последний известен был как лучший полководец своего времени, много путешествовавший по разным странам Европы и Азии, изучивший все боевые приемы лучших европейских и азиатских полководцев. Во время столкновения казаков с татарами первые ударили на врагов казаки; сами поляки уступили казакам право первого нападения на татар только после настоятельных убеждений со стороны Острожского, находившего казаков хотя и мало "збройными", но зато считавшего их в войнах с мусульманами более опытными, чем поляков. В 1516 году казаки, под начальством Ландскоронского, ходили походом под турецкий город Белгород, захватили там множество лошадей, рогатого скота и овец, но на обратном пути были настигнуты татарами и турками у озера Овидова, под Очаковом, разбили наголову неприятелей и возвратились домой с большой татарской и турецкой добычей. Этот год считается у польских летописцев уже годом значительного развития южнорусского казачества. В 1527 году на казаков черкасских и каневских жаловался крымский хан Саип-Гирей королю Сигизмунду II за то, что они, становясь под татарскими улусами, делали нападения на татар: "Приходят к нам черкасские и каневские казаки, становятся над улусами нашими на Днепре и вред наносят нашим людям; я много раз посылал к вашей милости, чтоб вы остановили их, но вы их остановить не хотели; я шел на московского князя, 30 человек за болезнью вернулись от моего войска: казаки поранили их и коней побрали. Хорошо ли это? Черкасские и каневские властители пускают казаков вместе с казаками неприятеля твоего и моего (то есть московского князя) казаками путивльскими по Днепру под наши улусы, и что только в нашем панстве узнают, дают весть в Москву". В 1528 году те же казаки, под начальством Хмельницкого старосты Предслава Ландскоронского, черкасского старосты Евстафия Дашковича, а также старост винницкого и брацлавского, принимали участие в походе под турецкий город Очаков; в этом походе казаки три раза разбили татар и взяли в добычу 500 коней и 30 000 голов скота.