Но до Санкт-Петербурга еще далеко, взоры Петра обращены к Крыму, для выхода к Черному морю нужно потеснить турок и занять азовское побережье. Азов сдается в 1696 г. «на договор, а не военным промыслом». Петр шумно празднует победу, начинает строить порт Таганрог, но понимает, что флота у России нет. Построенная на скорую руку, по старым чертежам из сырого леса флотилия неповоротлива, течет, гниет и разваливается. Армия не обучена, ленива и малочисленна. Надо учиться.
Петр решает снарядить посольство за границу в составе 250 человек. Цель великого посольства найти союзников против Османской империи, обучиться артиллерийскому делу, строительству флота, организации армии, завербовать и привезти спецов в этих вопросах. Сам Петр участвует в посольстве инкогнито, в качестве урядника Петра Михайловича. За два года 1697–1698 посольство посетило Ригу, Кенигсберг, Бранденбург, Голландию, Англию, Австрию, Вену. Завербовало в Россию несколько сотен специалистов, закупило образцы военного и железоделательного оборудования, но главной цели не достигло. Создать коалицию против Османской империи не удалось, Европа наоборот хлопотала о примирении с Турцией. У Петра появляется идея: взамен ускользнувшего из рук Черного моря обратить внимание на Балтийское. Петр заключает с Августом II — королем Польши тайный договор, в котором делят Шведские земли. России — Ингрия (Ленинградская область) и Карелия, Польше — Лифляндия и Эстландия.
Но великое посольство прерывается известием об очередном стрелецком бунте. Более 2-х лет царя не было в Москве, кто управлял государством — вопрос, кланы Милославских, Нарышкиных, Толстых, Лопухиных грызутся и разворовывают казну. Заканчивается это бунтом. К срочному возвращению Петра стрельцы были разбиты Шениным. Петр казнит до полутора тысяч стрельцов, обвиняет в организации бунта Софью, заставляет ее с сестрой Мартой, а заодно со своей женой Евдокией постричься в монахини, стрижет бороды у сановников государства, выдвигает на первое место любимчика Меньшикова, в декабре 1699 г. вводит новое летоисчисление, в 1700 г. упраздняет патриаршество в России. Проведена черта между старыми «потехами» и необходимостью серьезно управлять государством.