После окончания рады кошевой атаман Гордиенко марта 15-го дня отправил универсал через войскового товарища Грицька к казакам, кочевавшим возле рек Буга, Ингульца и Ингула, с просьбой не засиживаться возле рек и поспешить соединиться с кошевым для «войскового похода». Вместе с этим кошевой Гордиенко послал свой лист к польскому королю Станиславу Лещинскому, «покорно прося королевскую вельможность на сполную (общую) помощь и ратованье милой отчизны Украины». Станислав Лещинский избран был одной из польских политических партий «сапежинцев» при живом короле Августе II и имел поддержку у шведского короля Карла XII. Гордиенко, отправив своих посланцев к Лещинскому, ждал от него решительного ответа. Но посланцы Гордиенка попались в руки польским караульным и были представлены коронному гетману Синявскому; коронный же гетман, сторонник России, передал их Алексею Дашкову, русскому резиденту в Польше. Тогда письма, найденные при посланцах, были отправлены малороссийскому гетману Скоропадскому, который должен был показать их «знатным из запорожского войска (в Сечи), дабы они уведали то его, Гордеенково, злодейство».
Но Гордиенко тем не смутился. Оставаясь пока сам в Переволочне, он отправил к шведскому королю депутацию, одного полковника и 80 человек товариства, с известием о том, что запорожцы готовы, ради восстановления собственной свободы, служить верно королевскому величеству, жертвовать своей жизнью и с полным уверением за счастливый успех предпринимаемого святого дела. В то время главная квартира короля находилась все еще в местечке Великие Будища в 47 верстах от города Зинькова и 57 верстах от Полтавы. Туда и направился запорожский полковник с конвойным своим отрядом.
Марта 19-го числа депутаты прибыли в местечко Великие Будища, были приняты королем, допущены к его руке и потом угощались у шведского фельдмаршала Реншильда. Во все время пребывания своего в Будищах запорожские депутаты предавались веселью до излишества. На прощанье фельдмаршал Реншильд объявил десяти казакам, что они снова будут допущены к прощальной аудиенции у короля, но с условием не пить вина раньше обеда, так как король не переносит пьяных. Запорожцы, много пившие в последние дни, с трудом выдержали такое требование и простились с королем трезвыми. Зато после королевской аудиенции их великолепно угостил фельдмаршал Реншильд. Сам король сделал им прекрасные подарки и вручил два письма, одно к гетману Мазепе, другое ко всему запорожскому войску.
Вслед за отправкой депутатов двинулся из Переволочны и сам Гордиенко. Когда об этом движении кошевого стало известно в русском лагере, то начальники русской армии распорядились выслать против Гордиенка три полка с целью не допустить запорожцев до соединения со шведами. Таким образом, кошевому приходилось вступить с русскими в битву, чтобы очистить себе дальнейший путь к Великим Будищам. Запорожцы, перейдя границу своих владений, сделали два нападения на русских, одно у Царичанки, другое в городе Кобеляках. У Царичанки запорожцы в числе 800 человек атаковали бригадира Кампеля, у которого было три полка драгун численности в 3000 человек. Запорожцы изрубили 100 человек драгун да 90 человек из них захватили в плен, потеряв у себя только 30 человек. Из пленных москалей казаки отправили нескольких человек со шведскими посланцами к крымскому хану и просили его о помощи шведскому королю.
Такая удача под Царичанкой сразу дала запорожцам славу храброго войска и подняла столь высоко их знамя, что число их быстро увеличилось до 15 000 человек; к ним повыходили из недр лесов и болот скрывшиеся туда при нашествии шведов украинские жители, не желавшие против воли доставлять продовольствие войскам Карла. С таким числом людей запорожцы скоро овладели городками по рекам Орели, Ворскле и Днепру и везде оставляли в них по хорошему гарнизону.
Рассеяв русские отряды и закрепив за собой берега Днепра и его притоков Орели и Ворсклы, кошевой Гордиенко взял направление в местечко Диканьку в 25 верстах от Полтавы, чтобы свидеться там с Мазепой и оттуда идти в главную стоянку шведского короля Великие Будища. Перед своим выходом из Новосанджар кошевой Гордиенко оставил при возах от каждого куреня по 50 человек охраны, а жителям местечка отдал приказ в случае нападения на них московского войска уходить от русских за реку Ворсклу.
В это время гетман Мазепа, узнав о выходе к нему Гордиенка, выслал навстречу кошевому конвой в 2000 человек. Прийдя в Диканьку, Гордиенко направился прямо в тот дом, где находился Мазепа, и тут кошевого встретили самые знатные лица из гетманской свиты. Увидя гетманскую свиту, кошевой, в знак дружбы и уважения, поцеловал бунчук, который был принесен на тот случай. Самое свидание Гордиенка с Мазепой произошло в присутствии большого числа лиц запорожского товариства. Войдя в комнату Мазепы, кошевой увидел гетмана стоящим у стола, на котором лежали знаки гетманского достоинства, и отдал ему глубокий поклон. Поцеловав в знак уважения бунчук с развевавшимся на нем конским хвостом, кошевой сказал гетману такое слово:
«Мы, войско запорожское, и я, благодарим вас за то, что, в качестве начальника Украины, вы приняли к сердцу, как благонамеренный человек, положение, в котором вынужденно находится наше отечество, и за то, что вы начали освобождать его от владычества москалей. Так как мы уверены, что именно ввиду этого намерения, а не в видах собственного интереса или какой-либо особенной цели, вы выпросили покровительство короля Швеции, то мы решились помогать вам с верностью, подвергая опасности нашу жизнь и повинуясь вам во всем, так что вы имеете право нам приказывать для достижения желаемой цели. Мы умоляем вас взять на себя это бремя; чтобы облегчить тяжесть несения этого бремени, мы сделаем все возможное. Благодарим вас также за то, что вы изволили уведомить нас о намерении и благосклонности короля Швеции. Мы пришли с намерением просить покровительства у его величества и надеемся, при посредстве вашем, получить утверждение этого, как вы нам обещали. Имея также целью вступить в общее с вами дело и будучи готовы поклясться вам в послушании и верности, мы желаем, чтобы и вы также поклялись действовать с нами единодушно и оказали ваше содействие в защите отечества».