Słowo kozak ma przypuszczalnie tureckie korzenie i oznacza swobodnego, niezwiązanego więzami rodzinnymi najemnika. Pierwsze kozackie społeczności powstawały w XI–XV w. na terytoriach pogranicznych, w basenie Dniepru, Donu i Oki. Ich liczebność wzrastała ze względu na zmiany terytorialne i polityczne – m.in. likwidację księstwa kijowskiego, rozpad Wielkiej Ordy. Na przełomie XV/XVI w. były niezależnymi wspólnotami, które żyły z łupieżczych najazdów i dawały się mocno we znaki okolicznym państwom. Bliżej połowy XVI w. zarówno na terenach Ukrainy, jak i w dorzeczach Donu i Wołgi zaczęły masowo powstawać kozackie osady.
W historii państwa polsko-litewskiego pierwsze próby zaciągnięcia Kozaków na służbę państwową są odnotowane w 1489 r., kiedy występują oni w roli przewodników wojsk Jana Olbrachta. Wkrótce potem oddziały kozackie brały udział po stronie litewskiej w wojnie z Moskwą (1534–37). Na początku lat 50. XVI w. książę Dymitr Wiśniowiecki założył twierdzę na wyspie Chortyca na Dnieprze, która stała się centrum Siczy Zaporoskiej. Starostowie pograniczni utrzymywali ścisłe związki z Kozakami w celu obrony ziem pogranicznych przed najazdami Tatarów i w wojnach z Moskwą. Ostatecznie konieczność kontrolowania ich aktywności skutkowała zaciągiem 300 Kozaków na służbę państwową w 1572 r. Od tego momentu można mówić o powstaniu rejestru kozackiego na państwowym żołdzie. W Moskwie próby pozyskania Kozaków zaczynają się od ok. lat 40. XVI w.
W stepach pomiędzy Donem a Wołgą powstawała druga duża społeczność – przyszła Kozaczyzna dońska. Chociaż w XVI w. jej stosunki z Moskwą były nieregularne, Kozacy dońscy brali udział w walkach państwa moskiewskiego z Kazaniem (1552) i Astrachaniem (1556). Podbój tych chanatów stworzył możliwości dla powstania nowych społeczności kozackich – na rzekach Ural (ówcz.