Тетеря, приложивший немало усилий для того, чтобы гетманская булава оказалась вакантной, сразу же взял бразды правления в свои руки. Не жалея денег, он через верных людей, стал агитировать простых казаков высказаться за него на раде по выборам нового гетмана. Золото и серебро во все времена легко прокладывают путь к власти, тем более, что Тетерю многие помнили, как любимца Богдана Хмельницкого. Едва Юрий уехал, Тетеря в середине октября созвал раду в Чигирине, на которую помимо генеральной старшины, съехались полковники, сотники и часть казацкой черни приднепровских полков. Как и следовало ожидать, на раде мнения разделились не только (да, и не столько) по кандидатуре Тетери, сколько по вопросу о том, оставаться ли в подданстве короля или возвратиться на царскую службу. В конце концов, Павел Тетеря был избран гетманом, при условии, что он сохраняет верность королю Яну Казимиру и остается в подданстве Речи Посполитой.
Возможно, у короля не было особых оснований верить в легитимность избрания его гетманом, но Тетерю поддерживало большинство казаков и старшины, поэтому он был утвержден в должности. Новый гетман, однако, ставку делал больше не на своих казаков, в лояльности которых уверен не был, а на польские войска, требуя у короля подкреплений, и предостерегая, что в противном случае Войско может взбунтоваться и перейти на сторону татар. Это не было пустой угрозой: хорошо зная о слабости Польши, турецкий султан и татарский хан действительно вынашивали замысел присоединить правобережную Украйну к своим владениям.
Без поддержки короля положение Тетери грозило осложниться еще и потому, что в следующем году часть казаков отказалась ему подчиниться. Паволоцкий полк взбунтовался казаки перебили там всех поляков и на какое-то время фактически отделились от Тетери.
Все же, как бы то ни было, но правый берег Днепра определился с выборами гетмана и в целом сохранил верность Яну Казимиру. Напротив, на Левобережье продолжалась склока, усилившаяся из-за включения в борьбу за гетманскую булаву Ивана Брюховецкого.
Иван Мартынович Брюховецкий, сыгравший в дальнейшем видную роль в истории Малороссии, родился примерно в 1623 году, но происхождение его остается неясным. Яким Сомко говорил царскому посланнику Федору Ладыженскому: «…и Брюховецкий по баламутству его называетца гетманом; а у них же в Запорогах от веку гетмана не бывало, а были атаманы, также как и на Дону…, а особного де кошевого гетмана в Запорогах николи не бывало, то же учинено вновь… А Брюховецкому де верить нельзя, что он полулях, был Ляхом да крестился; а в войске он не служил и казаком не бывал».
Но и сообщению Сомко до конца доверять трудно, так как ему выгодно было опорочить своего соперника в глазах царского посла. Все же ходили разговоры, что казацких предков Брюховецкий не имел, а образование получил в униатской школе. Первые достоверные сведения о нем относятся к 1648 году, как о старшем джуре гетмана Богдана Хмельницкого, числящемся в реестре 1649 года среди казаков Чигиринской сотни. Сослуживцам он был больше известен, как Мартынец. Видимо, распознав в нем хозяйственного и предприимчивого человека, гетман сделал Брюховецкого распорядителем своего все разрастающегося имения. Ведь помимо наследственного поместья Субботово, доставшегося ему от отца, Чигирина, отданного королем ему «на булаву», гетман прибрал под свою руку еще и местечко Млиев, приносившее его бывшему владельцу Александру Конецпольскому ежегодный доход в 200 000 злотых. Всем этим хозяйством нужно было распоряжаться, присматривать за прислугой, ведением работ, сохранностью имущества. Поэтому в отсутствие гетмана всем этим руководил молодой, но расторопный и энергичный «старший слуга». Известно, что и строительством гетманской резиденции в Чигирине руководил также Брюховецкий. Богдан Хмельницкий верил ему и это доверие тот вполне оправдывал.
Когда Юрий Хмельницкий был отправлен отцом в Киев на учебу, Брюховецкий уехал вместе с ним и жил с гетманычем в одном доме, в качестве дворецкого и наставника. В 1657 году они вместе возвратились в Чигирин, затем вновь уехали в Киев, а оттуда летом 1658 года сбежали на Сечь. Когда год спустя Юрий был избран гетманом Войска Запорожского, то Брюховецкий, помог ему в этом содействием Запорожья, Ходили слухи, что он отвез на Сечь и солидную сумму денег, позволившую привлечь на сторону Хмельницкого низовое войско, что также вполне возможно, потому что для такого дела деньги были крайне необходимы. Участие запорожцев в раде требовало немалых затрат.
По-видимому, ко времени избрания Хмельницкого гетманом, Брюховецкому исполнилось около тридцати семи лет, возраст самый подходящий для удовлетворения честолюбивых замыслов. Отправив отряд запорожцев на выборы гетмана, сам Иван Мартынович предпочел некоторое время остаться на Сечи. Надо полагать, находиться в услужении, пусть даже и у гетмана, ему надоело, а его прежняя близость к Богдану Хмельницкому и богатый опыт хозяйственного управления, позволяли надеяться на быстрое выдвижение в запорожские атаманы. Так оно и произошло. Довольно скоро Брюховецкий приобрел у запорожцев такой авторитет, что они выбрали его кошевым атаманом. Конечно, этому во многом способствовало то обстоятельство, что на рубеже 60-х годов качественный состав низового войска в корне изменился. В первые месяцы своего правления Выговский, опасаясь возрастающего влияния кошевого Якова Барабаша, повел войну против Запорожской Сечи. В результате, часть низовиков вместе с кошевым атаманом ушла к Пушкарю, другие перебрались на Дон. Таким образом, настоящих потомственных запорожцев на Сечи практически не осталось. Однако, свято место пусто не бывает и вскоре Запорожье пополнилось голотой, которая не была включена в казацкий реестр или, наоборот, оказалась из него выписанной. Эти люди, в большинстве своем не имевшие ни семьи, ни крова, ни средств к существованию (своеобразные люмпен — казаки) находили себе пристанище на Сечи, где постепенно и стали преобладать. Их ряды значительно пополнились после разгрома восстания дейнек, когда многие сторонники Пушкаря также укрылись за днепровскими порогами. Эти пришлые люди не были природными запорожцами и даже казаками вообще, люто ненавидели «значных» и готовы были выступить на смертный бой с казацкой старшиной, в которой видели своих поработителей и врагов. Брюховецкому вряд ли удалось бы приобрести влияние среди прежних потомственных запорожцев, но с новыми он быстро нашел общий язык, используя их ненависть к «значным» казакам.
Все же после избрания его кошевым атаманом Брюховецкий вскоре вернулся к гетману Юрию и некоторое время находился при нем. После перехода Хмельницкого на сторону поляков, Брюховецкий сбежал из Чигирина в Лохвицу. Здесь, узнав о борьбе за гетманскую булаву Сомко и Золотаренко, он тоже решил включиться в нее.
Однако стать кошевым атаманом или даже гетманом на Сечи еще не означало, получить гетманскую булаву в Войске Запорожском. Помимо поддержки низовиков надо было решить, как минимум, две задачи: приобрести влияние хотя бы у части реестрового войска, а главное — заручиться поддержкой Москвы. Осуществление второй задачи имело первостепенное значение, поэтому воспользовавшись каким-то поручением одного из царских воевод, Брюховецкий лично отправился к царю. В Москве к нему отнеслись благосклонно, но он вскоре понял, что поддержку следует искать на месте у царских представителей в Малороссии и, в первую очередь, необходимо склонить на свою сторону местоблюстителя Киевской митрополии епископа Мефодия, чей авторитет в царском окружении был высок. Однако в это время Мефодий в борьбе за гетманскую булаву поддерживал Василия Золотаренко, который пользовался авторитетом и у царских воевод Шаховского, Чаадаева и других. За Сомко стояла большая часть Войска, однако, в Москве его недолюбливали из-за постоянных жалоб на царских ратных людей и требование помощи, в то время, когда у царского правительства и без того не хватало войск и денег.