В марте 1697 года в Западную Европу отправилось Великое посольство, главная цель которого заключалась в возрождении антитурецкой коалиции и подключении к ней новых союзников. Вместе с тем Петр надеялся за время своего пребывания за границей многому научиться. Именно поэтому он участвовал в поездке в качестве простого «десятника Петра Михайлова». Руководил посольством любимец царя Франц Лефорт. В отсутствие государя управление страной было поручено Л. Нарышкину, Б. Голицыну и П. Прозоровскому. Петр пробыл в Европе до августа 1698 года. За это время он посетил Амстердам, где три месяца работал корабельным плотником на верфи в Саардаме (он там не только плотничал, но успел побывать на многих важнейших фабриках и встретиться с ведущими учеными того времени), Лондон, Вену, Лейпциг, Дрезден и Прагу. Во всех этих странах посольство приглашало специалистов для работы в России. Петр встречался с английским королем Вильгельмом III и с австрийским императором Леопольдом I, но переговоры о союзе против Турции везде оказались безуспешными. Европа уже осознала, что может противостоять турецкой армии, и была теперь занята борьбой между Габсбургами и Бурбонами, которая грозила перерасти в большую войну. Возможно, Петр нашел бы понимание в Венеции, которая должна была отстаивать свои владения в Средиземном море, но туда ему попасть не удалось — из Москвы пришли вести о новом стрелецком бунте. Петр был в ярости: только перед самым отъездом Великого посольства был раскрыт заговор стрельцов, несколько человек казнили — и вот снова! Он устремился на родину.
С восстанием справились и без Петра — бунт был стихийным, стрельцами двигало лишь отвращение к нововведениям и нежелание служить по-новому. Привыкнув к тихой и сытой жизни в Москве, они не готовы были идти под турецкие пули. Стрельцы винили командиров-иноземцев, особенно «еретика Францка Лефорта», который, по их мнению, сознательно хотел погубить стрельцов.
В стрелецких полках зачитывали письмо Софьи, призывавшее их явиться к Новодевичьему монастырю. Требования бунтовщиков были просты: Немецкую слободу разорить, а немцев побить за то, что от них православие закоснело; бояр побить; государя в Москву не пустить и убить за то, что «почал веровать в немцев». Князь Борис Голицын распорядился выслать против стрельцов Семеновский и Преображенский полки. Под Новым Иерусалимом их остановили. Уговоры ни к чему не привели, и тогда правительственные войска тремя залпами подавили бунт.
Проведенное следствие так и не показало, кто стоял за мятежом. Это выяснил Петр, явившийся в конце августа из-за границы и начавший новое разбирательство. Более 1700 стрельцов, прошедших через первое расследование, было доставлено в Москву, и 17 сентября палачи приступили к делу. Вот тогда кто-то «с третьего огня» и признался, что было письмо от царевны Софьи. Петр лично допросил царевну и передал решение ее судьбы на усмотрение собора. Поскольку вина ее была не доказана, Софью постригли в монахини Новодевичьего монастыря. Но прежде на Красной площади, в Преображенском и перед Новодевичьим монастырем начались казни, в которых Петр и его приближенные приняли самое непосредственное участие. Всего было истреблено более 2500 человек, причем перед кельей Софьи повесили 195 стрельцов. Эти массовые пытки и казни, в которых Петр заставлял участвовать всех своих соратников, кажутся бессмысленной жестокостью. Но они преследовали определенную цель: Петр стремился узнать, не причастен ли к заговору кто-нибудь из его приближенных. Теперь вся высшая знать была повязана стрелецкой кровью.
С этого и начались настоящие петровские реформы. Даже первый день пребывания царя в Москве оказался символичным: царь не заехал ни во дворец, ни к жене, зато побывал у Лефорта, встретился с Анной Монс, ночевал в Преображенском, а наутро с шутками сам стриг бороды знатным вельможам. Через несколько дней бороды обрезали без всяких шуток — всеми своими действиями царь показывал, что противиться ему нельзя и вести страну он будет лишь в одном направлении — к Западу. Между тем бритье бород казалось почти святотатством — ведь еще недавно патриарх говорил, что бритые не достойны даже христианского погребения. Пытая стрельцов, Петр не забыл и о своей нелюбимой жене, Евдокии Лопухиной: 23 сентября 1698 года ее отправили в монастырь. Малолетнего царевича Алексея воспитывала тетка Наталья Алексеевна.