Побачивши, що Гордієнка скинути з уряду нелегко, Меншиков, щоб перетяти йому шлях на Україну, опанував з російським військом Омельники, Кременчук, Потоки, Монжалієвку та декотрі містечка по Орелі. Тільки й це не помогло: не діставши од царя ніякої навіть обіцянки про задоволення запорозьких вимог, Гордієнко вже рішив приєднатись до шведського короля і зробити останню спробу зброєю повернути Україну до вільного й незалежного життя. З тією метою 1 березня Гордієнко, лишивши Січ на наказного отамана Михайла Симонченка, рушив з тисячею запорожців з Січі на Кодаки і, прилучивши до себе виділи війська, вислані у Кодаки раніше, пішов на Переволочину. Там відбулася велика рада, у котрій брала участй також і запорозька переволочанська залога з полковником Нестулієм, і на тій раді всі запорозькі козаки ухвалили приєднатись до Мазепи й шведів.
У середині березня Гордіенко рушив з запорожцями на Царичанку, а проти нього туди ж з 3.000 російських драгунів вийшов бригадир Кемпель. Запорожці рішуче атакували драгунів і більше сотні з них порубали та стільки ж захопили у бранці, останніх же розігнали.
Після того Гордієнко погромив російське військо під Келебердою і почав добувати городи по Орелі й по Ворсклі. Український простий люд ще добре пам'ятав славу своїх заступників і оборонців його волі запорожців і почав озброюватись та прилучатись до запорожців, так що під рукою Гордієнка скоро згуртувалось біля 15.000 душ. Проте з повстанців запорожцям було користі дуже мало, бо проти гармат, рушниць та штиків російського війська вони мали тільки коси та вила. Відчинивши тими боями собі шляхи на Україну, Гордієнко пішов з військом у Диканьку, де перебував Мазепа. Бажаючи щастя Україні, запорозький кошовий отаман рішив забути свою зневагу до гетьмана, поєднатись з ним і навіть признати старшинування Мазепи, як гетьмана. Уступивши після урочистої зустрічі з боку Мазепиної старшини у хату, де жив Мазепа, і, заставши його біля столу, на котрому лежали військові клейноди, Гордієнко вклонився йому, поцілував на ознаку пошани гетьманський бунчук і у присутності запорозької й української старшини сказав Мазепі: "Військо Запорозьке і я дякуємо вам за те, що як гетьман України ви взяли до серця те становище, до котрого дійшла наша батьківщина, і почали визволяти її од московської влади. Ми певні, що саме з цією метою, а не з якоїсь персональної користі, ви попросили протекції шведського короля і тільки через те ми й зважились допомагати вам щиро, незважаючи на небезпеку нашого життя, і коритись вашій волі, так що ви волите наказувати нам, щоб досягти бажаної мети".Одповідаючи кошовому, Мазепа дякував Запорозькому Війську за довір'я і запевняв, що; покладаючись на шведського короля, він не мав на меті своєї користі, а вчинив так, не маючи вже сили терпіти неправдиві утиски на неньку Україну[9].
З Диканьки Гордієнко разом з Мазепою поїхав у Великі Будища, щоб стати перед очі шведського короля. У присутності запорозької старшини та почету короля Карла Гордієнко звернувся до нього з промовою латинською мовою[10], дякуючи од усього Війська Запорозького за те, що король обіцяв оборону як Війську Запорозькому, так і всьому народу українському проти загального ворога. За короля одповідав Гордієнкові теж латинською мовою шведський державний секретар Гермелін. Він висловив запорожцям королівську подяку за хоробрість під Царичанкою і радив скористатись щасливим випадком і добути собі стародавню волю та права. Ця промова після того була ще раз переказана слов'янською мовою, щоб могли зрозуміти її всі запорожці.
Після тих промов король частував Мазепу, Гордієнка й їхню старшину обідом, а на другий день у прнсутності короля відбулися наради про військові справи. По скінченні ж нарад з королем Гордієнко перевів своє військо під Полтаву, де сиділа велика московська залога, на південь, у Нові Санжари, і там розташувався табором.
Через якийсь час сюди, до кошового, дійшли вісті, що запорожцям дуже шкодить Чигиринський полковник Галаган[11], повідомляючи Меншикова й Голіцина про всі рухи запорозького вінська. Гнат Галаган був колись полковником на Запорожжі, пізніше ж перейшов до Мазепи і став полковником на Україні і найближчим після Орлика однодумцем Мазепи. З Мазепою разом він перейшов і до Карла XII, та тільки, роздивившнсь, що у шведів удесятеро менше війська, ніж у царя, і вгадавши, на чиєму боці буде перемога, він скористався випадком, коли був з козаками на під'їздах, і перебіг до російського війська, при чому захопив у бранці і привів до самого царя кілька десятків шведів. Цар пробачив Галаганові його тимчасову зраду і, призначивши його полковником охочекомонного полку, звелів служити собі проти запорожців, звичаї котрих Галаган добре знав.
Щоб покарати того запорозького зрадника, Гордієнко послав на Чигирин полк запорожців, та вони не змогли добути Галагана, бо Голіцин встиг прислати йому з Києва поміч.
З того часу почалися на Військо Запорозьке й Гордієнка пригоди. На Січі поміж запорожцями, що не пішли з Гордієнком та тими, що позбирались з рибальства, повстали сварки. Прихильники Гордієнка зачіпали московських людей, що сиділи у Кам'яному Затоні і хотіли добути ту кріпость, прихильники ж покори не давали того зробити. На початку квітня помірковані взяли гору і, скинувши позаочі Гордієнка з кошевства, обрали замість нього Петра Сорочинського.
Російський уряд уже тішився з приводу обрання на Січі нового кошового отамана, але не минуло й кількох тижнів, як настрій на Січі знову відмінився і більшість товарнства, до котрої приєднався і сам Сорочинський, ухвалила на раді обстоювати свої права й вольності зброєю і послати до кримського хана просити його помочі.
Тим часом на полки Гордієнка почав наступати з російським військом генерал Рене. Він вибив невеликі ватаги запорожців з Маячки та Нехворощі на Орелі і вирізав по тих містах всю людність разом з жінками й дітьми за те, що допомагали запорожцям, а всі оселі попалив. Далі він перейшов до Сокілки на Ворсклі і став там табором з сьома тисячами драгунів та піхоти. Квітня 17 до Сокілки ж на допомогу запорожцям прийшов шведський генерал Крузе з трьома тисячами війська і, оточивши разом з запорожцями табір росіян, почав добувати його. Становище Рене стало дуже скрутним. Він з російським військом мусив продиратися крізь ворогів і хоч вирвався з облоги, та втратив при тому 1.500 москалів.