В мае Заднепровский корпус соединился с ополчением Огинского и Сенявского. Русско-польско-литовская армия продвинулась к Львову, где находились войска Лещинского, состоявшие из его польских полков и части шведских сил, оставленных Карлом с генералом Крассау. Общее командование ими осуществлял бобруйский староста Ян-Казимир Сапега. Противники встретились у деревни Лидуховой, в нескольких километрах от городка Броды.
Единственным союзником у шведского короля на главной арене борьбы оставался Мазепа с 5000 казаков. Через него Карлу удалось получить поддержку из близлежащего района. 24 марта состоялась рада запорожских казаков, где они приняли решение перейти на службу к шведскому королю. В начале апреля в лагерь скандинавов прибыл кошевой атаман Запорожской Сечи Гордиенко с 8000 казаков, недовольных Москвой из-за ее посягательств на их старые вольности.
Разумеется, от казаков было мало проку в сражениях с регулярной армией (посильные им задачи — нападения на тылы, разведка, преследование разбитого противника), но запорожцы могли организовать быструю переправу через Днепр, ширина которого в низовьях достигала двух километров. Это было важно как для получения ожидаемой королем помощи, так и для обеспечения отступления. Поэтому Меншиков, не медля ни минуты, предпринял энергичные меры. Посланный из Киева отряд на лодках доплыл по Днепру до впадения в него Ворсклы, где у местечка Переволочна стояла большая часть речного флота запорожцев. 29 апреля солдаты разогнали казаков, сожгли все их суда и поплыли дальше к Сечи, находившейся ниже по течению Днепра на острове.
Тем временем земля подсохла, и Карл XII решил, что в качестве базы, опираясь на которую он бы мог ждать старых или новых союзников, ему необходима какая-либо крепость. Самой удобной казалась Полтава, стоявшая на Ворскле, километрах в ста выше от места ее впадения в Днепр. Вокруг этого города шведская армия и начала собираться к середине апреля.