В ответ на этот опустошительный набег козаки двинулись в следующем году на Молдавию. Во главе их стоял человек огромной физической силы, ломавший иногда руками подковы и прозванный за это Подковой. Война длилась полтора года и в конце 1577 года завершилась вступлением козаков в молдавскую столицу Яссы. Однако победа была непрочной, против козаков выступили турки и, по их настоянию, сам Баторий. Подкова отступил с добычей в Запорожье, но по дороге один польский магнат изменнически залучил его к себе и отослал к Баторию. По требованию турецкого султана, Баторий велел обезглавить Подкову.
Взамен отрубленной головы Подковы у козачества выросло сто других. Нашелся некто, на звавший себя Александром, братом обезглавленного гетмана. Баторий, желавший во что бы то ни стало сохранить мир с Турцией, выступил против Александра, разбил его рать, а его самого взял в плен и отправил, в Константинополь. Но на смену посаженному на кол Александру тотчас явился другой предводитель, назвавший себя Петром, сыном Александра. Под начальством Петра козаки возобновили нападения на Молдавию.
Турецкий султан, молдавский господарь, крымский хан — все слили свои голоса в хоре жалоб на козаков. Выходило так, что все они лишь беззащитные агнцы, которых преследуют свирепые козаки. Даже ужасный набег 1575 года татары объяснили всегдашними обидами со стороны козаков.
Баторий решил прибегнуть к энергичным мерам. Помимо внешнеполитических соображений, его побуждало к этому и желание уничтожить главное препятствие на пути к совершенному слиянию Южной Руси с Польшей — вернее, к совершенной полонизации (ополячению) Южной Руси. Ему хотелось установить на Украине прочный общественный порядок (в польском понимании), то есть закрепостить большую часть населения, а часть оставить свободной и использовать ее в целях защиты от татар. Козаки являлись главным оплотом украинской народности. Поэтому уничтожение или хотя бы подчинение их вытекало из задач также и внутренней полигики Батория.
Осенью 1578 года Стефан Баторий заключил представителями украинского козачества соглашение. По этому соглашению из среды козачества составлялся особый полк на постоянном жалованье у правительства. На штатных козаков доставлялся особый список, реестр, вследствие чего они получили название реестровых.
Реестровые козаки должны были присягнуть и верности королю и дать обязательство не воевать без приказания короля ни с Крымом, ни с Молдавией. За реестровыми признавалась личная свобода и, кроме того, целый ряд специальных прав: судить их могли только по соглашению с их старшúной, да и то лишь за убийство и насилия, с них не взыскивали налогов и поборов и т. п.
Король надеялся таким путем привлечь на свою сторону наиболее влиятельную часть козачества. Но этот расчет удался лишь отчасти. Реестровые знали, что их значение определяется в глазах польского правительства именно всей массой заштатного козачества, подкреплявшего их своей мощью. Поэтому они вовсе не склонны были вступать в резкий конфликт с этой массой.
И все же известного расслоения в козачестве Баторий, несомненно, добился. Реестровые упорно отстаивали свои привилегии, они не хотели совершенно уподобиться заштатным козакам. Формальное подчинение правительству налагало на них серьезные обязательства. Поэтому в последующие козацких восстаниях, когда правительство посылало реестровых для усмирения непокорных, они оказывались всякий раз в очень трудном положении. Большей частью дело кончалось расколом внутри самих реестровых: часть сражалась в стане правительственных войск, часть переходила к козацкой вольнице. Иногда реестровые переходили к восставшим всем составом (так случилось во время восстания Хмельницкого), иногда же они, напротив, отстаивали интересы правительства.
Мероприятие Стефана Батория, способствовавшее классовому расслоению козачества и тем причинившее ему большой вред, принесло ему и немалую пользу. Оно как бы узаконило претензии козачества на привилегированное положение в ряду других сословий, и всякий раз, как польское правительство покушалось уничтожить козацкие вольности, козаки торжественно предъявляли грамоту Батория.
Наряду с этим реформа Батория в известной мере содействовала укреплению Запорожской Сечи: отныне на тех, кто не был включен в реестр, но тем не менее стремился сохранить независимое положение, польские власти на Украине смотрели как на ослушника правительственных распоряжений. Если они желали избежать закрепощения, им ничего не оставалось делать, кроме как бежать «за пороги» — и уже не временно, а навсегда. Таким образом, Сечь, эта запорожская община непризнанных козаков, получила новые многочисленные пополнения.