Najazdy tatarskie na południowo-wschodnie ziemie Rzeczypospolitej zmusiły trzymających straż graniczną starostów ukrainnych do wykorzystania oddziałów prywatnych, takich jak Kozacy zaporoscy.

W początkach XVI w. wyprawy na ułusy tatarskie organizowali starostowie, jak choćby Ostafij Daszkiewicz czy Przecław Lanckoroński. Wzajemne wyprawy Kozaków na pobrzeża Morza Czarnego, a Tatarów na Ukrainę powodowały poważne zadrażnienia w stosunkach polsko-tureckich. Kozacy z okolic Kaniowa i Czerkas brali udział w wyprawie starosty włodzimierskiego Fedora Sanguszki w 1545 r. na Oczaków, który zdobyli i spalili. Przejęcie w 1569 r. województw ukrainnych przez Koronę (unia lubelska) nie zmieniło sytuacji, gdyż stan obronności tych ziem nie uległ poprawie. Zmienić to mogło wykorzystanie Kozaczyzny i wprzęgnięcie jej w system obronny kresów południowo-wschodnich Rzeczypospolitej po 1569 r. Konflikty pomiędzy ówczesną elitą władzy a Kozakami, którzy wyłamywali się spod władzy starostów i organizowali „chadzki” nad Morze Czarne, utrudniały jednak te zamierzenia. W 1568 r. król Zygmunt August nakazał Kozakom opuszczenie Niżu, domagając się, aby podjęli służbę „przy zamkach naszych”, a w 1572 r. powierzył zorganizowanie pierwszego oddziału kozackiego szlachcicowi Janowi Badowskiemu, który miał podlegać bezpośrednio hetmanowi koronnemu. Ten jeden z pierwszych rejestrów Kozaków na żołdzie Rzeczypospolitej liczył ok. 300 mołojców. Za Stefana Batorego w 1578 r. podobne zadanie powierzono staroście czerkaskiemu i kaniowskiemu Michałowi Wiśniowieckiemu, który zwerbował oddział liczący 530 Kozaków na wojnę z Moskwą. Były to początki funkcjonowania rejestrowych Kozaków w służbie Rzeczypospolitej.