В 1561 году перекопский царь писал польскому королю Сигизмунду-Августу о желании 24 белогородских татарских казаков «оказать службу литовскому государю идти на землю московскую»; приложенные при письме перекопского царя имена белогородских казаков все восточного происхождения, каковы: Аглаберды, Аличембей, Акмалла-ага, Бакай-ага, Бассан-али, Джарлы-ага, Чабан-ага и другие[13].

Вслед за известием о татарских казаках находим известие и о южнорусских. По мнению Максимовича, исторически известными становятся на Украине казаки уже с 1471 года, когда Киевское княжество обращено было в воеводство[14]. По известию летописца XVII века Мартина Бельского, в 1489 году, во время преследования татар, ворвавшихся в Подолию, сыном короля Казимира IV, Яном Альбрехтом, впереди литовского войска шли до притока Буга, Саврана, казаки, хорошо знавшие местность Побужья[15]. По указанию Антоновича, именем казаков, в 1491 году, назвались крестьяне в Червонной Руси, восставшие на защиту своих прав[16]. Но документальное свидетельство о существовании украинских казаков в первый раз встречается в 1499 году в уставной грамоте великого князя Литовского Александра о воеводских доходах, данной киевскому войту и мещанам: «Который казаки з верху Днепра и с инших сторон ходят водою на низ, до Черкас и далей, а што там здобудуть, с того со всего воеводе десятое (десятую долю) мають давати; а коли рыбы привозят з верху, або з низу, просолныи(ой) и вялыи(ой) до места киевского, тоди мает осичник воеводин то осмотрети и обмитити (пометить) и мает на город взяти от бочки рыб по шести грошей, а от вялых рыб и свежих десятое (десятую штуку). А коли привезут до места киевского рыбу свежую, осетры, тогды не мают их целиком продавати, оли-ж (но) мусить осинник от каждого осетра по хребтине взяти, а любо (либо) от десяти осетров десятого осетра»[17]. В 1503 году, по свидетельству Архива Юго-Западной России, становятся известными черкасские казаки и казаки князя Дмитрия[18]. Те и другие составляли уже иррегулярное войско в Литве; они организованы были по мысли правительства для защиты границ Литвы от набегов татар и состояли в ведении так называемых старост, то есть управителей областей, городов и замков государства[19]. Такие казаки набирались самими старостами и нередко прозывались именами или фамилиями самих же старост: казаки князя Дмитрия, казаки князя Ружинского, казаки Мировицкого[20]. В это же время становятся известными особые роты, или военные отряды в казачьем быту: так, под 1503 годом польский хронист Пясецкий упоминает о Щуровой казачьей роте в городе Черкассах[21]. В 1508 году одна часть казаков, под начальством брацлавского и виленского старосты, князя Константина Ивановича Острожского, разгромила наголову загон татар, грабивших пограничные области Литовской Руси; другая часть казаков, под начальством «славного казака Полюса-русака», разбила другой загон татар[22]. В 1512 году казаки, вместе с поляками и украинскими насельниками, участвовали в погоне за татарской ордой, ворвавшейся в южные пределы Литовского великого княжества. Начальниками над казаками и поляками были князь Константин Иванович Острожский и каменецкий староста Предслав Ландскоронский.

Последний известен был как лучший полководец своего времени, много путешествовавший по разным странам Европы и Азии, изучивший все боевые приемы лучших европейских и азиатских полководцев. Во время столкновения казаков с татарами первые ударили на врагов казаки; сами поляки уступили казакам право первого нападения на татар только после настоятельных убеждений со стороны Острожского, находившего казаков хотя и мало «збройными», но зато считавшего их в войнах с мусульманами более опытными, чем поляков. В 1516 году казаки, под начальством Ландскоронского, ходили походом под турецкий город Белгород, захватили там множество лошадей, рогатого скота и овец, но на обратном пути были настигнуты татарами и турками у озера Овидова, под Очаковом, разбили наголову неприятелей и возвратились домой с большой татарской и турецкой добычей[23]. Этот год считается у польских летописцев уже годом значительного развития южнорусского казачества. В 1527 году на казаков черкасских и каневских жаловался крымский хан Саип-Гирей королю Сигизмунду II за то, что они, становясь под татарскими улусами, делали нападения на татар: «Приходят к нам черкасские и каневские казаки, становятся над улусами нашими на Днепре и вред наносят нашим людям; я много раз посылал к вашей милости, чтоб вы остановили их, но вы их остановить не хотели; я шел на московского князя, 30 человек за болезнью вернулись от моего войска: казаки поранили их и коней побрали. Хорошо ли это? Черкасские и каневские властители пускают казаков вместе с казаками неприятеля твоего и моего (то есть московского князя) казаками путивльскими по Днепру под наши улусы, и что только в нашем панстве узнают, дают весть в Москву»[24]. В 1528 году те же казаки, под начальством Хмельницкого старосты Предслава Ландскоронского, черкасского старосты Евстафия Дашковича, а также старост винницкого и брацлавского, принимали участие в походе под турецкий город Очаков; в этом походе казаки три раза разбили татар и взяли в добычу 500 коней и 30 000 голов скота[25].

С этого времени казаки стали приобретать особенную известность, и этому способствовал немало «знаменитый казак» Евстафий, или Остап-Дашкович, сперва литовский воевода, потом черкасско-каневский староста, уроженец города Овруча, человек православной веры. Евстафий Дашкович воевал сперва против турок и побывал в плену у татар (в 1523 году), служил несколько лет великим русским князьям, Ивану и Василию, помогая им в войне против поляков, затем снова возвратился в Литву к Сигизмунду[26] и получил в управление города Черкассы и Канев[27], на правом берегу Днепра ниже Киева. Управляя этими городами, он привлек к себе такое множество казаков, что сделал оба города надолго ядром всего южнорусского казачества. В 1531 году на город Черкассы сделал нападение крымский хан Саадат-Гирей; Дашкович мужественно оборонял черкасский замок от татар, а потом, через два года после этого, представил на сейме в Пиотркове особый проект защиты границ Литовского княжества против татарских вторжений. В этом проекте Дашкович высказал необходимость построения поблизости к татарам, на одном из малодоступных островов Днепра, замка и содержания в нем постоянной стражи из казаков в 2000 человек, которая, плавая по реке на чайках, препятствовала бы татарам переправляться через Днепр. К этим 2000 казаков Дашкович предлагал прибавить еще несколько сот человек, которые бы добывали в окружностях необходимые припасы и доставляли их казакам на острова. Предложение Дашковича всем участникам сейма понравилось, но не было приведено в исполнение[28].