Коренным образом переориентируя внешнюю политику России, царь крайне тяжело переживал незавершенность успешна начатых им южных дел. Психологически ему очень сложно было смириться с мыслью, что все те огромные усилия и средства, вложенные в борьбу с Турцией, в сущности, оказались напрасными. И все же Петр в последний раз решает вырвать у Порты дипломатическими средствами то, что он не успел осуществить силой оружия. Направляя в Константинополь для переговоров с Турцией своего посла Е. И. Украинцева, он вновь требует реализации своей программы-максимум, которую русская делегация отстаивала еще на Карловицком конгрессе.
В августе подготовка посольства Украинцева была закончена. Понимая всю сложность возложенных на нее задач, Петр решает подкрепить свою дипломатию внушительной демонстрацией военно-морской мощи России. Украинцев и сопровождавшие его лица прибыли в Константинополь на тридцатипушечном корабле «Крепость», который до Керчи сопровождала эскадра из 22 военных судов. Однако гром артиллерийского салюта с «Крепости», возвестивший о прибытии русской миссии, вызвал в султанском дворце совершенно иную реакцию. В правящих кругах Турции стали раздаваться голоса о страшной опасности, нависшей над Блистательной Портой с севера, и о немедленной ликвидации этой угрозы до того, как царь добавит к этому кораблю десятка три ему подобных. Эти настроения в османском правительстве, естественно, не могли не сказаться на позиции турецкой стороны в ее переговорах с русскими дипломатами. Требования Украинцевым Керчи и свободы русской торговли встретили решительный отпор турок, заявивших, что это будет возможно лишь тогда, «когда Турское государство падет и вверх ногами обратится». Послы морских держав, заинтересованные в продолжении войны, активно подводили султана к идее реванша и отбрасывания России за пределы Таврии. Украинцев писал царю, что «послы английский и голландский во всем держат крепко турецкую сторону, и больше хотят им всякого добра, нежели тебе, Великому государю». Переговоры застыли на мертвой точке, что давало пищу для слухов о их провале и подготовке обеих сторон к новой войне.
Ситуация, сложившаяся на переговорах в Константинополе, активизировала усилия русской дипломатий по консолидации антишведских сил в рамках военной коалиции.
11 ноября 1699 г. в селе Преображенском, под Москвой, был заключен союз с Августом II, предусматривавший немедленное вступление Саксонии в войну со Швецией. Россия обязалась начать боевые действия после заключения мира с Турцией. Заключая этот договор в качестве курфюрста саксонского, Август II обязался склонить к вступлению в союз и Польшу. Кроме того, договор определил и театр военных действий: Россия в Ингрии и Карелии, а Саксония в Лифляндии и Эстляндии, что, в сущности, означало разграничение будущих владений союзников в Прибалтике.
Союзный договор с Данией, согласованный Петром с датским послом еще в апреле, был ратифицирован царем 26 ноября 1699 г. Согласно его положениям, договаривающиеся стороны обязывались оказывать друг другу военную помощь в случае нападения на одну из них третьей державы. Хотя объект действия союза не указывался в тексте договора, но под ним, естественно, подразумевалась Швеция. Для России договор вступал в силу лишь после заключения ею мирного соглашения с Турцией.
Подписание Петром договора с Данией завершило создание антишведской коалиции — Северного союза в составе России, Саксонии и Дании.
Вступая в Северный союз, каждый из его участников преследовал прежде всего свои собственные цели, которые в той или иной мере вступали в противоречия с планами других алиаторов. Август II и поддерживающая его польско-литовская магнатерия не были заинтересованы в усилении России, которое могло произойти в случае ее утверждения на берегах Балтики. Лифляндский дворянин на саксонской службе И. Р. Паткуль предлагал Августу II ограничить владения России лишь Карелией и Ижорскими землями и ни в коем случае не позволять Петру овладеть Нарвой. Он внушал королю, что «если царь удержит Нарву за собой, то он легко овладеет Ревелем, потом всею Эстляндией, наконец, со временем и Лифляндиею». Август II полностью разделял это мнение, считая, что польская Лифляндия должна превратиться в «оплот против Швеции и Москвы».