После взятия Азова Петр решил строить и усиливать флот. Он задумал закрепиться не только на Черном море.
Молодой царь твердо решил вернуть земли у побережья Балтики, потерянные в Смутное время. А для флота нужны были грамотные моряки. Обучиться тогда они могли только в Европе. И царь отправил за границу для обучения «навигацкому» (морскому) и инженерному делу более шести десятков юношей. Сам Петр последовал за ними — он тоже задумал получить образование за границей. Но не только эта задача стояла перед царем.
Нужно было показать себя Европе, заключить выгодные договоры, закупить оружие, инструменты и пригласить в страну иноземных мастеров и офицеров, пока не выучились свои. Всем этим должно было заняться посольство, которое назвали Великим. Его возглавили адмирал Франц Лефорт, генерал Федор Головин и думный дьяк Прокофий Возницын. В свите посольства ехал урядник Преображенского полка Петр Михайлов — сам царь. Считается, что именно Великое посольство положило начало российской дипломатии в ее современном понимании, дало толчок европеизации Руси. Царь Петр I отправился в Европу учиться всему — от кораблестроения до политики, всему, что нужно для блага государства. Он посетил множество стран. В Бранденбурге Петр обучился артиллерийскому делу и получил аттестат, в котором указано, что «господин Петр Михайлов везде за исправного, осторожного, благоискусного, мужественного и бесстрашнаго огнестрельного мастера и художника признаваем и почитаем быть может». Четыре с половиной месяца провел царь в Голландии, которая тогда считалась одной из самых сильных европейских держав.
Голландские корабелы были прекрасными мастерами, но опирались на собственный опыт и не все изображали на чертежах. Петру же нужны были именно чертежи, теория, благодаря которой можно было бы рассчитывать пропорции корабля. Он отправился в Англию, где четыре месяца учился чертежному искусству.
Вернувшись на континент, Петр поехал в Вену, а оттуда собрался в Венецию, но тут до него дошли страшные вести — в Москве взбунтовались стрелецкие полки. Царь поспешил домой, но когда 25 августа 1698 г. он добрался до столицы, бунт был уже подавлен, зачинщики казнены, а более тысячи человек сослано. Однако Петру этого показалось мало. Он велел вернуть ссыльных. Почти всех их страшно пытали, а затем казнили. В пытках принимал участие сам Петр. А во время двух массовых казней царь велел стать палачами своим приближенным. После этого Петр вообще покончил со стрелецким войском. Шестнадцать московских полков расформировали, стрельцов с семьями разослали по городам. Старая Московская Русь уходила в прошлое. Петр, никого не щадя, вел страну в новую эпоху.