Уже в предыдущем году, познакомившись с неудобствами Белого моря, Пётр начал думать о перенесении своих морских занятий на какое-нибудь другое море. Он колебался между Балтийским и Каспийским; ход русской дипломатии побудил его предпочесть войну с Турцией и Крымом, и тайной целью похода назначен был Азов — первый шаг к выходу в Чёрное море. Шутливый тон скоро исчезает; письма Петра становятся лаконичнее, по мере того как обнаруживается неподготовленность войска и генералов к серьёзным действиям. Неудача первого похода заставляет Петра сделать новые усилия. Флотилия, построенная в Воронеже, оказывается, однако, малопригодной для военных действий; выписанные Петром иностранные инженеры опаздывают; Азов сдаётся в 1696 г. «на договор, а не военным промыслом». Пётр шумно празднует победу, но хорошо чувствует незначительность успеха и недостаточность сил для продолжения борьбы. Он предлагает боярам схватить «фортуну за власы» и изыскать средства для постройки флота, чтобы продолжать войну с «неверными» на море. Бояре возложили постройку кораблей на «кумпанства» светских и духовных землевладельцев, имевших не меньше ста дворов. Остальное население должно было помогать деньгами. Построенные «кумпанствами» корабли оказались позднее никуда не годными, и весь этот первый флот, стоивший населению около 900 тыс. тогдашних рублей, не мог быть употреблён ни для каких практических целей.
Одновременно с устройством «кумпанств» и ввиду той же цели, то есть войны с Турцией, решено было снарядить посольство за границу для закрепления союза против «неверных». «Бомбардир» в начале Азовского похода и «капитан» в конце, Пётр теперь примыкает к посольству в качестве «волонтёра Петра Михайлова» с целью ближайшего изучения кораблестроения. 9 марта 1697 г. посольство двинулось из Москвы с намерением посетить Вену, королей английского и датского, папу, голландские штаты, курфюрста бранденбургского и Венецию. Первые заграничные впечатления Петра были, по его выражению, «малоприятны»: рижский комендант Дальберг слишком буквально понял инкогнито царя и не позволил ему осмотреть укрепления; позднее Пётр сделал из этого инцидента casus belli.
Пышная встреча в Митаве и дружественный приём курфюрста бранденбургского в Кенигсберге поправили дело. Из Кольберга Пётр поехал морем вперёд, на Любек и Гамбург, стремясь скорее достигнуть своей цели — второстепенной голландской верфи в Саардаме, рекомендованной ему одним из московских знакомцев. Здесь Пётр пробыл восемь дней, удивляя население маленького городка своим экстравагантным поведением. Посольство прибыло в Амстердам в середине августа и осталось там до середины мая 1698 г., хотя переговоры были кончены уже в ноябре 1697 г. В январе 1698 г. Пётр поехал в Англию для расширения своих морских познаний и оставался там три с половиной месяца, работая преимущественно на верфи в Дептфорде. Главная цель посольства не была достигнута, так как штаты решительно отказались помогать России в войне с Турцией; зато Пётр употребил время пребывания в Голландии и в Англии для приобретения новых знаний, а посольство занималось закупками оружия и всевозможных корабельных припасов, наймом моряков, ремесленников и т. п. На европейских наблюдателей Пётр произвёл впечатление любознательного дикаря, заинтересованного преимущественно ремёслами, прикладными знаниями и всевозможными диковинками и недостаточно развитого, чтобы интересоваться существенными чертами европейской политической и культурной жизни. Его изображают человеком крайне вспыльчивым и нервным, быстро меняющим настроение и планы и не умеющим владеть собой в минуты гнева, особенно под влиянием вина. Обратный путь посольства лежал через Вену. Пётр испытал здесь новую дипломатическую неудачу, так как Европа готовилась к войне за испанское наследство и хлопотала о примирении Австрии с Турцией, а не о войне между ними. Стеснённый в своих привычках строгим этикетом венского двора, не находя и новых приманок для любознательности, Пётр спешил покинуть Вену для Венеции, где надеялся изучить строение галер. Известие о стрелецком бунте вызвало его в Россию; по дороге он успел лишь повидаться с польским королём Августом, и здесь, среди трехдневного непрерывного веселья, мелькнула первая идея заменить неудавшийся план союза против турок другим планом, предметом которого, взамен ускользнувшего из рук Чёрного моря, было бы Балтийское.
Прежде всего предстояло покончить со стрельцами и со старым порядком вообще. Прямо с дороги, не повидавшись с семьёй, Пётр проехал к Анне Монс, потом на свой Преображенский двор. На следующее утро, 26 августа 1698 г., он собственноручно начал стричь бороды у первых сановников государства. Стрельцы были уже разбиты Шеиным под Воскресенским монастырём и зачинщики бунта наказаны. Пётр возобновил следствие о бунте, стараясь отыскать следы влияния на стрельцов царевны Софьи. Найдя доказательства скорее взаимных симпатий, чем определённых планов и действий, Пётр тем не менее заставил постричься Софью и её сестру Марфу. Этим же моментом Пётр воспользовался, чтобы насильственно постричь свою жену, не обвинявшуюся в прикосновенности к бунту. Брат царя Иоанн умер ещё в 1696 г.; никакие связи со старым не сдерживают больше Петра, и он предаётся со своими новыми любимцами, среди которых выдвигается на первое место Меншиков, какой-то непрерывной вакханалии, картину которой рисует Корб. Пиры и попойки сменяются казнями, в которых царь сам играет иногда роль палача. С конца сентября по конец октября 1698 г. было казнено более тысячи стрельцов. В феврале 1699 г. опять казнили стрельцов сотнями. Московское стрелецкое войско прекратило своё существование.
Указ от 20 декабря 1699 г. о новом летосчислении формально провёл черту между старым и новым временем. 11 ноября 1699 г. был заключён между Петром и Августом тайный договор, которым Пётр обязывался вступить в Ингрию и Карелию тотчас по заключении мира с Турцией, не позже апреля 1700 г.; Лифляндию и Эстляндию, согласно плану Паткуля, Август предоставлял себе. Мир с Турцией удалось заключить лишь в августе. Этим промежутком времени Пётр воспользовался для создания новой армии, так как «по распущении стрельцов никакой пехоты сие государство не имело». 17 ноября 1699 г. был объявлен набор новых 27 полков, разделённых на 3 дивизии, во главе которых стали командиры полков Преображенского, Лефортовского и Бутырского. Первые две дивизии (Головина и Вейде) были вполне сформированы к середине июня 1700 г.; вместе с некоторыми другими войсками, всего до 49 тыс., они были двинуты в шведские пределы на другой день по обнародовании мира с Турцией (19 августа). К неудовольствию союзников, Пётр направил свои войска к Нарве, взяв которую он мог угрожать Лифляндии и Эстляндии. Только к концу сентября войска собрались у Нарвы; только в конце октября был открыт огонь по городу. Карл ХII успел за это время покончить с Данией и неожиданно для Петра высадился в Эстляндии. Ночью с 17 на 18 ноября русские узнали, что Карл XII приближается к Нарве. Пётр уехал из лагеря, оставив командование принцу де Круа, незнакомому с солдатами и неизвестному им — и восьмитысячная армия Карла XII, усталая и голодная, разбила без всякого труда сорокатысячное войско Петра.
Надежды, возбуждённые в Петре путешествием по Европе, сменяются разочарованием. Карл XII не считает нужным преследовать далее такого слабого противника и обращается против Польши. Сам Пётр характеризует своё впечатление словами: «тогда неволя леность отогнала и ко трудолюбию и искусству день и ночь принудила». Действительно, с этого момента Пётр преображается. Потребность деятельности остаётся прежняя, но она находит себе иное, лучшее приложение; все помыслы Петра устремлены теперь на то, чтобы одолеть соперника и укрепиться на Балтийском море. За восемь лет он набирает около 200 тыс. солдат и, несмотря на потери от войны и от военных порядков, доводит численность армии с 40 до 100 тыс. Стоимость этой армии обходится ему в 1709 г. почти вдвое дороже, чем в 1701 г.: 1 810 000 руб. вместо 982 000. За первые шесть лет войны уплачено было сверх того субсидий королю польскому около полутора миллиона. Если прибавить сюда расходы на флот, на артиллерию, на содержание дипломатов, то общий расход, вызванный войной, окажется 2,3 млн. в 1701 г., 2,7 млн. в 1706 г. и 3,2 млн. в 1710 г. Уже первая из этих цифр была слишком велика в сравнении с теми средствами, которые до Петра доставлялись государству населением (около 1,5 млн.). Надо было искать дополнительных источников дохода. Первое время Пётр мало заботится об этом и просто берет для своих целей из старых государственных учреждений не только их свободные остатки, но даже и те их суммы, которые расходовались прежде на другое назначение; этим расстраивается правильный ход государственной машины. И всё-таки крупные статьи новых расходов не могли покрываться старыми средствами, и Пётр для каждой из них принуждён был создать особый государственный налог. Армия содержалась из главных доходов государства — таможенных и кабацких пошлин, сбор которых передан был в новое центральное учреждение — ратушу. Для содержания новой кавалерии, набранной в 1701 г., понадобилось назначить новый налог («драгунские деньги»); точно так же — и на поддержание флота («корабельные»). Потом сюда присоединяется налог на содержание рабочих для постройки Петербурга («рекрутные», «подводные»); а когда все эти налоги становятся уже привычными и сливаются в общую сумму постоянных («окладных»), к ним присоединяются новые экстренные сборы («запросные», «неокладные»). И этих прямых налогов, однако, скоро оказалось недостаточно, тем более что собирались они довольно медленно и значительная часть оставалась в недоимке. Рядом с ними придумывались поэтому другие источники дохода. Самая ранняя выдумка этого рода — введённая по совету Курбатова гербовая бумага — не дала ожидавшихся от неё барышей. Тем большее значение имела порча монеты. Перечеканка серебряной монеты в монету низшего достоинства, но прежней номинальной цены дала по 946 тыс. в первые три года (1701–1703), по 313 тыс. — в следующие три; отсюда были выплачены иностранные субсидии. Однако скоро весь металл был переделан в новую монету, а стоимость её в обращении упала наполовину; таким образом, польза от порчи монеты была временная и сопровождалась огромным вредом, роняя стоимость всех вообще поступлений казны (вместе с упадком стоимости монеты). Новой мерой для повышения казённых доходов была переоброчка в 1704 г. старых оброчных статей и отдача на оброк новых; все владельческие рыбные ловли, домашние бани, мельницы, постоялые дворы обложены были оброком, и общая цифра казённых поступлений по этой статье поднялась к 1708 г. с 300 до 670 тыс. ежегодно. Далее, казна взяла в свои руки продажу соли, принёсшую ей до 300 тыс. ежегодного дохода, табака (это предприятие оказалось неудачным) и ряда других сырых продуктов, дававших до 100 тыс. ежегодно. Все эти частные мероприятия удовлетворяли главной задаче — пережить как-нибудь трудное время.