В 1698 году во время нахождения Петра в длительном отъезде в Европу стрельцы поднялись в очередной раз под знаменами староверов, подбадриваемые слухом о смерти царя за границей, и пошли на Москву. Оставленный Петром главным в стране Федор Ромодановский растерялся и попытался вступить с мятежниками в переговоры. Узнав об этом, Петр бросился в Россию. В этот год он окончательно понял, что из преображенцев настоящего органа тайного сыска не создать, они хороши только как каратели уже выявленных злоумышленников. В письме с дороги он ругает не оправдавшего его надежд Ромодановского, а с ним и всю свою несовершенную систему государственной безопасности: «Зело мне печально и досадно на тебя, для чего ты сего дела в розыск не вступил. Богу тебя судить! Я не знаю, откуда на вас такой страх бабий! Неколи ничего ожидать с такой трусостью!»
Этот стрелецкий бунт был просмотрен Ромодановским, как свидетельствует история, из-за загруженности оставленного главным в стране князя-кесаря другими государственными заботами и традиционной причиной — очередным долгим запоем в отсутствие царя. Мятеж, как и в 1682 году, вызревал долго и готовился почти в открытую. Высланные на польские границы стрельцы сбегали, засылали в Москву своих разведчиков, смогли связаться с заключенной в Новодевичьем монастыре опальной царевной Софьей и убедиться в широкой поддержке своего выступления среди москвичей. В Преображенский приказ к Ромодановскому регулярно доставляли таких лазутчиков и агитаторов, утверждавших на улицах, что Петр погиб за границей, а немцы-еретики привезут вместо него своего агента-двойника для истребления Руси и ее старой веры, что нужно всем подниматься и идти на Кремль, опять сажать на трон свергнутую Софью Алексеевну. И при всем этом известие о том, что четыре стрелецких полка, перебив командиров, идут боевым порядком брать Москву, Ромодановского выдернуло из затянувшегося празднования и ввергло во временный шок. Имея в тот момент всю полноту власти в России и орудие Преображенского приказа под рукой, Федор Юрьевич несолидно заметался, а затем затеял мирные переговоры со стрельцами, чем и разгневал своего сверхрешительного правителя. Ведь положение для власти Петра действительно складывалось угрожающее: прорвись стрельцы в Москву, их там встретила бы мощная пятая колонна в лице заточенной в монастырь Софьи, антипетровского боярства, собственных стрелецких семей и огромного количества москвичей, бывших совсем не в восторге от «прогрессивных» реформ Петра через всеобщее принуждение к ним.
Мятеж 1698 года смогли подавить еще до приезда Петра в Москву. Не дожидаясь приказов Ромодановского, полковник Гордон, шотландец на русской службе, вывел навстречу стрелецким войскам свои новые части иноземного строя, рассеяв плохо организованную массу стрельцов огнем своей артиллерии на переправе их мятежного войска через подмосковную речку Истру. Только после этого преображенцы Ромодановского приступили к массовым розыскам, арестам, пыткам и казням. Пытаясь оправдать свою нерешительность, Ромодановский даже попытался ввести Петра в заблуждение, преуменьшая масштабы проблемы. Он повесил полсотни главных зачинщиков бунта, отпустив остальных стрельцов на свободу, объяснив царю с их слов, что речь не шла о попытке захвата власти и возведения на трон Софьи, а изведенные нуждой стрельцы просто без спроса пошли в Москву к своим семьям, помыться в банях и сытно поесть. Но эта неуклюжая попытка представить масштабный политический мятеж и заговор массовой самоволкой оголодавшего воинства Ромодановскому не удалась. Петр обрушил на своего оплошавшего главу сыска и заместителя по управлению страной потоки брани, приказал вновь арестовать и пытать уже отпущенных стрельцов. Под пытками преображенцев те признали факт замысла взять Москву с боя и поменять в России власть, и тогда уже начался тот самый массовый стрелецкий розыск.
Царь возглавлял это жестокое следствие, лично допрашивая даже многих рядовых стрельцов, дважды выезжая в монастырь для допросов содержащейся здесь своей сестры Софьи, подозреваемой в подстрекательстве стрельцов к бунту. Все это кончилось знаменитым «утром стрелецкой казни», когда на Красной площади под личным руководством царя казнены около двухсот участников мятежа, а в несколько следующих дней еще около двух тысяч обвиняемых. Такого масштаба политических репрессий страна не видела со времен опричных казней 1570 года при Иване Грозном. Сам царь Петр по примеру Ивана лично взял топор. Присутствовавший при казни в числе других иностранных дипломатов австрийский посланец Иоганн Корб даже подсчитал, что Петр сам отрубил головы пятерым осужденным (по другим свидетельствам, царь обезглавил более десятка стрельцов). Ромодановский своей свирепостью при этом розыске и казнях вернул себе утраченное в глазах царя доверие, но это касалось только лично его, а не его службы сыска.