Царь принял обе рекомендации. Вместе с Ф. А. Головиным он разработал подробный наказ-инструкцию незнатному и умному Украинцеву. Подготовили для него и корабль «Крепость». Весь флот, построенный в Воронеже и предназначенный для войны с Турцией, должен был сопровождать корабль посла до Керчи. Вместо военных действий флот должен был совершить дипломатическую демонстрацию.
Через неделю, 9 апреля, Петр указом назначает послом в Нидерланды А. А. Матвеева - первого постоянного дипломатического представителя России за рубежом. Этому образованному, выдающемуся впоследствии дипломату Петр дал ответственные поручения - побудить Голландию способствовать заключению мира России с Турцией, привлечь ее к войне на Балтике на стороне России или же, в случае неудачи, не допустить ее союза со Швецией.
Между тем 46-пушечная «Крепость» взяла курс на Стамбул, Петр же с Азовского моря вернулся в Воронеж, оттуда - в Москву.
В столице царя ждали новые дела и заботы. Уже около месяца находилось здесь шведское посольство по случаю возведения на престол Карла XII. Швеция в преддверии все той же войны за испанское наследство очень хотела бы обезопасить свои восточные границы. Для этого посольство должно было добиться подтверждения условий Кардисского мирного трактата 1661 г., который сохранил за Швецией балтийское побережье.
Для Петра подтверждение условий мира 1661 г., с одной стороны, нежелательно, поскольку цели России и Швеции в балтийском вопросе расходились; с другой - отказ от подтверждения показал бы враждебные намерения России, что было тогда неразумно. Выход он нашел. Шведов (а их приехало 150 человек) приняли очень торжественно: с войсками по пути следования, приемом в Столовой палате Кремля. Правда, Петр нарядился не в пышные одеяния московских монархов, а в простой кафтан; длинную речь посла слушать не пожелал, показав, что лучше бы - покороче.
Во время шести деловых встреч речь шла об обряде подтверждения договора. От присяги на евангелии и крестоцелования царь отказался. Договорились, что стороны обменяются грамотами, подтверждающими Кардисский трактат, а русское посольство приедет в Стокгольм по этому случаю.
Одновременно Петр вел переговоры с генералом Карловичем - личным представителем Августа II как курфюрста саксонского. Здесь дело выглядело непростым. Получалось, что в союз с Россией против Швеции вступала только Саксония. Хотя Август II одновременпо был и королем польским, Речь Посполитая на переговорах с Карловичем «отсутствовала».
Август II давал понять, что впоследствии, после оформления русско-саксонского союза, и Речь Посполитая присоединится к договору. Но все это выглядело весьма проблематично.
Петр видел насквозь Августа II. Но приходилось брать в союзники, как говорится, кого господь послал. Но он не торопился, в отличие от короля, который настаивал на начале военных действий против Швеции в декабре 1699 г.
11 ноября Петр подписал договор. Август II сделал это раньше, отправляя Карловича в Москву. Русско-датский договор, заключенный 21 апреля, оформили 23 ноября, когда произошел обмен его подписанными текстами. Оба акта - первые международно-правовые документы, подписанные лично русским царем. Предшественники Петра никогда этого не делали, ограничиваясь ратификацией договоров, их утверждением - давали торжественное обещание, целовали крест. Подписи же ставили только послы. Петр сломал эту традицию, шедшую со времен Киевской Руси. Поскольку подпись Петра означала одновременно и ратификацию, процедура оформления договора упрощалась, а авторитет его повышался.
Оба договора оформили Северный союз России, Дании и Саксонии в предполагавшейся войне со Швецией. Но мира с Турцией еще не было. Этим занимался Украинцев. 28 августа на рейде Стамбула, прямо против султанского сераля, бросил якорь русский корабль «Крепость». И султан, и его подданные в изумлении - не верилось, что русские способны построить такие суда и пересечь на них Черное море.
Перед Украинцевым стояла задача не из легких, даже труднее, чем у Возницына в Карловцах. К тому времени, когда он явился в Стамбул, обстановка в Европе обострилась. Если в сентябре 1698 г. Англия, Голландия и Франция подписали соглашение о мирном разделе испанского наследства, то летом следующего года они же составили новый договор о том же, поскольку умер Карл II, король испанский. На смену мирной перспективе надвигалась неизбежность войны.