Уже в предыдущем году, познакомившись с неудобствами Белого моря, Пётр начал думать о перенесении своих морских занятий на какое-нибудь другое море. Он колебался между Балтийским и Каспийским; ход русской дипломатии побудил его предпочесть войну с Турцией и Крымом, и тайной целью похода назначен был Азов — первый шаг к выходу в Чёрное море. Шутливый тон скоро исчезает; письма Петра становятся лаконичнее, по мере того как обнаруживается неподготовленность войска и генералов к серьёзным действиям. Неудача первого похода заставляет Петра сделать новые усилия. Флотилия, построенная в Воронеже, оказывается, однако, малопригодной для военных действий; выписанные Петром иностранные инженеры опаздывают; Азов сдаётся в 1696 г . «на договор, а не военным промыслом». Пётр шумно празднует победу, но хорошо чувствует незначительность успеха и недостаточность сил для продолжения борьбы. Он предлагает боярам схватить «фортуну за власы» и изыскать средства для постройки флота, чтобы продолжать войну с «неверными» на море. Бояре возложили постройку кораблей на «кумпанства» светских и духовных землевладельцев, имевших не меньше ста дворов. Остальное население должно было помогать деньгами. Построенные «кумпанствами» корабли оказались позднее никуда не годными, и весь этот первый флот, стоивший населению около 900 тыс. тогдашних рублей, не мог быть употреблён ни для каких практических целей.
Одновременно с устройством «кумпанств» и ввиду той же цели, то есть войны с Турцией, решено было снарядить посольство за границу для закрепления союза против «неверных». «Бомбардир» в начале Азовского похода и «капитан» в конце, Пётр теперь примыкает к посольству в качестве «волонтёра Петра Михайлова» с целью ближайшего изучения кораблестроения. 9 марта 1697 г . посольство двинулось из Москвы с намерением посетить Вену, королей английского и датского, папу, голландские штаты, курфюрста бранденбургского и Венецию. Первые заграничные впечатления Петра были, по его выражению, «малоприятны»: рижский комендант Дальберг слишком буквально понял инкогнито царя и не позволил ему осмотреть укрепления; позднее Пётр сделал из этого инцидента casus belli.
Пышная встреча в Митаве и дружественный приём курфюрста бранденбургекого в Кенигсберге поправили дело. Из Кольберга Пётр поехал морем вперёд, на Любек и Гамбург, стремясь скорее достигнуть своей цели — второстепенной голландской верфи в Саардаме, рекомендованной ему одним из московских знакомцев. Здесь Пётр пробыл восемь дней, удивляя население маленького городка своим экстравагантным поведением. Посольство прибыло в Амстердам в середине августа и осталось там до середины мая 1698 г ., хотя переговоры были кончены уже в ноябре 1697 г . В январе 1698 г . Пётр поехал в Англию для расширения своих морских познаний и оставался там три с половиной месяца, работая преимущественно на верфи в Дептфорде. Главная цель посольства не была достигнута, так как штаты решительно отказались помогать России в войне с Турцией; зато Пётр употребил время пребывания в Голландии и в Англии для приобретения новых знаний, а посольство занималось закупками оружия и всевозможных корабельных припасов, наймом моряков, ремесленников и т. п. На европейских наблюдателей Пётр произвёл впечатление любознательного дикаря, заинтересованного преимущественно ремёслами, прикладными знаниями и всевозможными диковинками и недостаточно развитого, чтобы интересоваться существенными чертами европейской политической и культурной жизни. Его изображают человеком крайне вспыльчивым и нервным, быстро меняющим настроение и планы и не умеющим владеть собой в минуты гнева, особенно под влиянием вина. Обратный путь посольства лежал через Вену. Пётр испытал здесь новую дипломатическую неудачу, так как Европа готовилась к войне за испанское наследство и хлопотала о примирении Австрии с Турцией, а не о войне между ними. Стеснённый в своих привычках строгим этикетом венского двора, не находя и новых приманок для любознательности, Пётр спешил покинуть Вену для Венеции, где надеялся изучить строение галер. Известие о стрелецком бунте вызвало его в Россию; по дороге он успел лишь повидаться с польским королём Августом, и здесь, среди трехдневного непрерывного веселья, мелькнула первая идея заменить неудавшийся план союза против турок другим планом, предметом которого, взамен ускользнувшего из рук Чёрного моря, было бы Балтийское.