Не успели еще докончить Кодакские укрепления, как атаман Сулима, прославившийся своими удачными морскими походами, поспешил уничтожить эту преграду. Предводительствуя несколькими тысячами запорожцев, он внезапно ночью ворвался в крепость, истребил малочисленный ее гарнизон, начальника его француза Морьона велел казнить, а укрепления разрушить (1635 г.). Этим событием возобновилась ожесточенная борьба казачества с поляками. Гетман Конецпольский угрозами заставил реестровых схватить и выдать Сулиму с главными его товарищами в руки правительства. Они были казнены в Варшаве. Перед казнию Сулима, Бог весть зачем, принял католичество. Одному из осужденных его товарищей, по имени Павлюку, канцлер Фома Замойский (сын знаменитого Яна Замойского) выспросил у короля пощаду. И этот-то Павлюк явился во главе следующего казацкого восстания.
Причиною нового восстания был все тот же усиливающийся гнет от подстарост и других старостинских урядников в королевских землях, от управителей и арендаторов-жидов в панских имениях; поборы и повинности все увеличивались, и продолжалось стремление шляхты к закрепощению простого народа, со включением так наз. выписчиков или тех людей, за которыми она не признавала казацкого звания. Недовольные, по обычаю, уходили на Запорожье. Когда они вновь скопились там в большом числе, то выбрали своим гетманом Павлюка и подняли знамя бунта (1637 г.). Реестровые со своим старшим Саввою Кононовичем хотели остаться покорными Речи Посполитой. Новоизбранный гетман послал на него несколько тысяч запорожцев с полковником Скиданом, который захватил Кононовича в Переславле. Павлюк велел его расстрелять. Украйна закипела шайками поднявшихся хлопов, которые бросились грабить и жечь панские дворы и фольварки, причем тщательно забирали всякое оружие.
С особою силою мятеж разлился в обширной Заднепровской Вишневечине. Шляхта спасалась бегством в укрепленные города и замки. Коронный гетман Конецпольский с кварцяным войском сторожил тогда южную границу от угрожавших ей турок и потому двинул против мятежников своего товарища или польного гетмана Николая Потоцкого с небольшим отделом кварцяных жолнеров. Эти жолнеры также готовы были взбунтоваться от неуплаты жалованья. Но Потоцкий их успокоил. Сын одного из самых крупных украинских землевладельцев, он возбудил к деятельной обороне своих товарищей, украинских панов, которые явились к нему на помощь с вооруженными отрядами; в их среде главное место занимал Еремия Вишневецкий.
В лагере восставших казаков не было единодушия: большая часть реестровых осталась верна полякам и соединилась с Потоцким; а другая часть хотя и пристала к запорожцам, но действовала осторожно и неохотно. Сам Павлюк оказался ниже своей задачи. Он звал на помощь себе крымского хана; но тот его обманул; таким образом, пропущено было лето, т. е. самое удобное для казаков время, и только в декабре казацкий гетман двинулся из Запорожья на Украйну, где действовал полковник Скидан. Под Кумейками (к югу от Канева) он неожиданно столкнулся с Потоцким, у которого передовым отрядом начальствовал известный разбойник и лихой наездник Самуил Лащ. Произошла жестокая битва. Несмотря на превосходство в числе и отчаянную храбрость запорожской голоты, польское военное искусство, более крепкая дисциплина, лучшее вооружение и артиллерия начали брать верх. Тогда конница реестровых и сам Павлюк с главными помощниками покинули поле битвы. Поляки ворвались в казацкий табор, и битва обратилась в беспощадное избиение голоты. Но тут выдвинулся своим мужеством и распорядительностью некто Димитрий Томашевич Гуня: он сумел устроить новый табор, в котором до ночи оборонялся со своим отрядом, а ночью ускользнул с ним из рук победителей. Павлюк с остатками разбитого войска окопался в местечке Боровице. Здесь православный украинский пан Адам Кисель выступил посредником между поляками и казаками. Он поклялся на том, что жизнь Павлюка и его товарищей будет пощажена, и уговорил казаков выдать их в знак своей покорности. (Скидан и Гуня скрылись.) Уполномоченные Запорожского войска присягнули вновь на исполнение Куруковского договора: казакам окончательно предоставлено было право выбирать только старшину полковую; а войсковую, т. е. старшого и есаулов, назначал коронный гетман; все лодки на Запорожье они должны были сжечь, а приставшую к ним чернь выдать. При войске должен был состоять правительственный комиссар, который, собственно, и ведал его делами и резиденцией которого назначен казацкий город Трахтемиров. Старшим над реестровыми теперь поставлен был переяславский полковник Ильяш Караимович. Он подписал присягу вместе с пятью другими полковниками, Черкасским, Каневским, Чигиринским, Корсунским и Белоцерковским. Присяга была скреплена войсковою печатью и подписью войскового писаря Богдана Хмельницкого, который в этой войне вместе с названными полковниками оставался верным Речи Посполитой. Присяжная грамота помечена 24-м декабря 1637 года.
Сейм 1638 года не признал для себя обязательной клятву Адама Киселя о пощаде Павлюка с товарищами, и они были казнены в Варшаве. Рассказывают, что перед казнию на голову Павлюка хотели надеть раскаленную железную корону и дать ему в руки такой же скипетр, потому будто бы, что он хвастал взять самую Варшаву и там короновать себя королем. Но Владислав IV избавил его от таких продолжительных мук.
Мятеж был подавлен только на правой стороне Днепра. Благодаря случившемуся тогда в нем ледоходу, сообщения с Заднепровской Украйной на время прекратились, и там шайка гультяев продолжала свирепствовать в панских имениях, т. е. жечь и грабить панские дворы, избивать панскую челядь и жидов. Но когда Днепр покрылся льдом, Потоцкий перевел свои хоругви на левую сторону и успел до некоторой степени очистить ее от казацких шаек. Около этого времени до 4000 запорожцев хотели пробраться в Персию, чтобы наняться к шаху и служить ему в войне с турками; но дорогою они, по приглашению донцов, соединились с ними и вместе взяли у турок Азов.
Казачество, особенно в Заднепровской Украйне, притихло только до весны. Зима была самым неудобным временем для казацкой войны, потому что лишала их обычных прикрытий и убежищ. Только летом казаки приобретали полную свободу для своих действий. Тогда к их услугам являлись болота, камыши, лесные поросли, яры и балки; тут они были в своей стихии и, опираясь на эти убежища, могли действовать с большею уверенностию и отвагою.
Меж тем, разносимые по Украине преувеличенные слухи о страшных жестокостях, с которыми паны и жолнеры торжествовали свою победу, о намерении ляхов истребить весь православный русский народ, о всевозможных притеснениях и вымогательствах жидов-арендаторов и т. п. распаляли народные страсти и возбуждали непримиримую ненависть к господству ляхов и жидов. Весною 1638 года в Заднепровье снова поднялись толпы голоты, снова запылали панские дворы и хутора и полилась кровь. Во главе восстания теперь стали, уже отличившиеся в предыдущем году и спасшиеся из рук ляхов, Остраница и Гуня, полковники Скидан, Путивлец, Филоненко и др. Выбранный гетманом войска Запорожского, Яцко Остраница или Остранин (из города Остра), расположился табором в Базавлуцкой Сечи, и в марте 1638 года издал универсал или послание ко всему казачеству обеих сторон Днепра. В этом послании он рассказывает, как некий Геродовский, начальствовавший в городе Остре, прошлою зимою мучил отца Остранина, семидесятилетнего старика, за то, что он не мог доставить наложенное на него количество сыру и масла для собак Геродовского, а после и за то, что у него не оказалось венгерского вина, которого потребовал начальник при своем посещении. От мук и побоев старик умер. Геродовский велел избить до полусмерти также и брата Остранинова, который после того убежал в Сечь. Затем универсал указывал малорусскому народу вообще на тиранство ляхов, на избиваемых отцов и братьев, на матерей, жен и сестер, подвергаемых бесчестью, обливаемых водою в трескучие морозы или запрягаемых в плуги наподобие волов и подгоняемых жидовскими бичами, по приказу ляхов; указывал на гонения православных, насильственное обращение в унию и т. д. Остранин призывал народ вооружаться против ляхов и спешить к нему на соединение. Он советовал делать это втайне от реестровых казаков, называя их «отродками и отщепенцами», которые ради своих выгод и корысти помогали ляхам в предыдущей Кумейской войне. Этот универсал посредством расторопных казаков был разослан в округи Черкасский, Белоцерковский и Уманский на правой стороне Днепра, в Переяславский, Нежинский и Дубенский на левой. Начальники восстания, кроме того, звали на помощь и крымцев, и донцов; но крымцы отказали, а донцы были тогда заняты Азовом. Реестровые казаки не пристали к запорожцам и сражались против них в рядах польского войска.
Предводимые Остранином и Скиданом, запорожцы с Днепра двинулись на его левую сторону в лесистое и болотистое пространство между Пслом и Ворсклою, во владения Вишневецкого, и взяли его городок Голтву на Псле. Польный гетман Николай Потоцкий отрядил сюда своего родственника Станислава Потоцкого с наемною немецкою пехотой, польскими жолнерами и реестровыми казаками. После тщетных усилий выбить запорожцев из Голтвы Станислав Потоцкий отступил к городу Лубнам на Суле. Остранин и Скидан, увлеченные первым успехом, перешли в наступление и ударили на Потоцкого; но от польской артиллерии и немецкой пехоты понесли такие потери, что ночью ушли вверх по Суле. Это отступление случилось очень некстати: на помощь им полковник Путивлец вел более 2000 казацкой голоты, в том числе 500 донцов. Потоцкий, пользуясь уходом Остранина, напал на Путивльца. После длившейся целый день упорной обороны гультяи, по своему обычаю, от великой самонадеянности быстро перешли к унынию и вероломству: они выдали Путивльца с товарищами и изъявили покорность. Но рассвирепевшие жолнеры, не обращая внимания на переговоры, бросились на казаков и всех перебили. Потоцкий после того отступил к Киеву, которым тщетно пытались овладеть казаки. Остранин меж тем, подкрепив себя новыми толпами голоты, двинулся опять вниз по Суле. Против него выступил князь Еремия Вишневецкий во главе войска, собранного из панских отрядов; с ним соединился и Станислав Потоцкий. Столкновение произошло у местечка Жолнина, где казаки заняли позицию, защищенную болотами и лесистыми порослями, и начали отабориваться, т. е. укреплять вокруг себя табор из возов. Но Вишневецкий не дал им времени докончить укрепление и стремительным ударом разорвал их табор.