Одновременно с подготовкой дела кораблестроения подготовлялось исполнение и других пунктов намеченного плана, т. е. посылка русских людей за границу для обучения морскому делу и отправление к европейским дворам посольства, в составе которого намеревался путешествовать сам царь. 22 ноября 1696 года «комнатным стольникам» был объявлен указ, ехать «в разные государства учиться всяким наукам» – назначение совсем необычное, новое, немало поразившее многие дворянские семьи. Из этих стольников 39 человек должны были отправиться в Италию и 22 в Голландию и Англию. Все это были члены виднейших русских фамилий: из 61 стольника – 23 носили княжеские титулы. Здесь были князья Голицыны, Долгорукие, Хилковы, князь Куракин, Черкасский, Урусов, Репнин, Трубецкой и др. Для них была составлена Петром инструкция, по которой их занятия должны были состоять в изучении мореплавания, именно в ознакомлении с морскими картами и компасом, в приобретении знания всех снастей корабля и умения управлять им, как в обыкновенном плавании, так и во время боя и т. д. Эти стольники выезжали за границу в течение зимы 1697 года, каждый на собственные средства.
Между тем снаряжалось и «великое посольство», которое должно было посетить римского цесаря, английского и датского королей, Нидерландские штаты, бранденбургского курфюрста, папу и Венецианскую республику. Послами были назначены Лефорт, Головин и думный дьяк Возницын с огромной свитою, всего около 250 человек. Целью посольства было укрепление союза против турок, «подтверждение древней дружбы и любви для общих всему христианству дел, к ослаблению врагов креста Господня, султана турского и хана крымского, и к вящему приращению государей христианских». Наряду с этим, посольству дано было поручение нанять иностранных офицеров, мастеров и закупить необходимые для кораблестроения материалы. Петр собственноручно написал послам инструкцию, в которой приказывал: «К службе морской сыскать капитанов добрых, которые б сами в матросах бывали и службою дошли чина, а не по иным причинам, поручиков и подпоручиков, а также и мастеровых людей: ропшлагеров, машт-макеров и диммакеров, блокмакеров, шлюпмакеров и др. с снастьми довольными». Но, конечно, одной из главных целей посольства было дать возможность примкнувшему к нему отряду «волонтеров» поработать на знаменитых корабельных верфях. Этот отряд волонтеров состоял из 30 человек Преображенских бомбардиров, ближайших друзей Петра, среди которых был будущий любимец Александр Меншиков. Отряд разделялся на десятки, и над одним из них десятником был Петр Михайлов, урядник Преображенского полка, сам царь. Одушевлявшее тогда Петра настроение он выразил в надписи, вырезанной на печати, которою он запечатывал свои письма из-за границы: «Аз есмь в чину учимых и учащих мя требую».
Посольство тронулось из Москвы 9 марта и направилось через Ригу и Митаву во владения курфюрста Бранденбургского, в Пруссию. В Либаве Петр расстался с послами и путь из Либавы до Кенигсберга, где тогда находился бранденбургский курфюрст, сделал морем. Вскоре же по приезде он посетил курфюрста Фридриха III в строгом инкогнито и провел с ним часа полтора, разговаривая на голландском языке за стаканом венгерского. Время в ожидании посольства он посвятил в Кенигсберге изучению артиллерии под руководством главного инженера прусских крепостей фон Штернфельда. Этот Штернфельд по окончании обучения выдал Петру аттестат, в котором свидетельствовал, что в Петре Михайлове он заметил очень «понятливую особу» и что он, как в Кенигсберге, так и в приморской крепости Пилау, «ежедневно благоупомянутого господина Петра Михайлова не только в теории науки, но и в практике, частыми работами собственных рук его обучал и упражнял. В том и другом случае в непродолжительное время, к общему удивлению, он такие оказал успехи и такие приобрел сведения, что везде за исправного, осторожного, благоискусного, мужественного и бесстрашного огнестрельного мастера и художника признаваем и почитаем быть может».