Когда же Август был принужден отречься, Петр стал искать ему замену. На польском троне он хотел видеть не марионетку, а сильного, самостоятельного государя, который сумел бы и править страной, и командовать войсками на поле боя. Поначалу его выбор пал на принца Евгения Савойского – одного из величайших полководцев того времени, который был в зените славы. Евгений отвечал, что благодарен царю за оказанную честь, но ответ будет зависеть от воли его государя – императора Иосифа; императору же Евгений написал, что, как верный вассал, прослуживший своему государю двадцать лет, он и ныне целиком полагается на его решение. Императора терзали сомнения: он сознавал все преимущества того, чтобы на польском троне оказался его преданный, энергичный слуга, но побаивался задевать Карла, а провозглашение Евгения королем неминуемо привело бы к войне со Станиславом, на стороне которого выступил бы шведский король. Поэтому он отложил принятие окончательного решения и написал Петру, что, поскольку принцу Евгению предстоит новая кампания, необходимо подождать до следующей зимы.
Но Петр ждать не мог. Коль скоро армия Карла готовилась выступить из Саксонии, ему был необходим, причем немедленно, дружественный к России польский король. Он обратился к Якубу Собескому, сыну бывшего польского короля Яна, но тот отказался, сочтя эту честь чересчур опасной. Петр начал переговоры с Ференцем Ракоци, венгерским патриотом, поднявшим восстание венгров против имперского владычества, и тот согласился принять корону, если она будет официально предложена ему польским сеймом. Дальнейших шагов не последовало: Карл выступил из Саксонии и двинулся к границам России.
С отречением Августа Петр лишился и второго союзника. Из первоначального тройственного альянса Саксонии, Дании и России осталась только Россия. Теперь «сия война над одними нами осталась», – говорил он. Оказавшись со шведами один на один, Петр прилагал усилия к тому, чтобы склонить Карла к мирному соглашению или, если не получится, найти новых союзников, которые помогли бы ему избежать разгрома, представлявшегося всей Европе неминуемым.
В то время война расколола Европу на две коалиции, в каждой из которых Петр пытался найти посредника или союзника. В 1706 году Андрей Матвеев предложил предоставить Генеральным штатам 30 000 лучших русских солдат для ведения войны с Францией, если великие морские державы убедят Карла согласиться на мир с Россией. Ответа от Голландии не последовало, и Петр обратился с просьбой о помощи и посредничестве к нейтральным державам – Пруссии и Дании. Но и эти попытки не увенчались успехом. Тогда в марте 1707 года Петр попросил выступить посредником между ним и Швецией Людовика XIV, обещая ему в случае успеха прислать русские войска для ведения войны против Англии, Голландии и Австрии. Петр предлагал безоговорочно вернуть шведам Дерпт и выплатить большую контрибуцию за право оставить за собой Нарву. Он настаивал лишь на том, чтобы сохранить Петербург и устье Невы. Людовик обещал содействие.
Обращался Петр и к Англии. Еще в 1705 году, когда в Москву прибыл Чарльз Уитворт, новый дипломатический представитель королевы Анны, Петр надеялся, что тот сможет убедить свою государыню посодействовать разрешению конфликта на Балтике. Уитворт был не прочь оказать Петру услугу и ходатайствовал в Лондон о дипломатическом вмешательстве в пользу царя, но безуспешно. В конце 1706 года Петр велел Матвееву из Гааги отправляться в Англию и просить королеву, чтобы та пригрозила Швеции войной, если Карл не заключит мира с Россией. Условия мира царь оставлял на усмотрение королевы и желал сохранить за Россией только ее «исконные вотчины», то есть Ижорскую землю и, разумеется, Неву на всем ее протяжении. Если бы официальные переговоры ни к чему не привели, Матвеев должен был попытаться негласно склонить на свою сторону самых влиятельных британских министров – Мальборо и Сиднея Годольфина. Петр не особо обольщался на этот счет и говорил: «Не чаю, чтоб Малбурка [Мальборо] до чего склонил, понеже чрез меру богат, однако ж обещать тысяч около двух сот или больше».
Перед тем как отправиться из Голландии в Англию, Матвеев встретился с Мальборо в Гааге. Вот что писал герцог об этой беседе Годольфину в Лондон: «Московский посол побывал у меня и от имени своего государя рассыпался в уверениях в глубочайшем почтении к Ее Величеству… в знак чего он решил отправить в Англию своего единственного сына [на обучение]…Я надеюсь, что Ее Величество позволит это, ибо очевидно, что иные его пожелания по части переговоров Вы вряд ли сможете удовлетворить».