Во главе Преображенского приказа стоял князь Федор Юрьевич Ромодановский. Он происходил из старинного рода, восходившего к легендарному Рюрику, и по своему воспитанию и возрасту принадлежал к консервативному боярству. Тем не менее Ф.Ю. Ромодановский одним из первых одобрил преобразовательную деятельность Петра. Во время заграничного путешествия царя князь Ф.Ю. Ромодановский остался наместником в Москве. Он представлял царскую особу, носил придуманный Петром титул князя-кесаря и именовался «величеством». Ромодановский был беспощадным руководителем политического сыска. Ему доводилось не только самолично допрашивать подозреваемых, но и принимать участие в публичных казнях. Во время массовой казни стрельцов Ромодановский собственноручно отсек головы четырем стрельцам. Даже Петр порой упрекал князя в излишней жестокости. Царь писал ему из-за границы: «Зверь! Долго ли тебе людей жечь? И сюды раненые от вас приехали». Несмотря на короткие размолвки, Ромодановский был наиболее преданным сподвижником Петра и пользовался его полным доверием.

После смерти князя-кесаря в 1717 г. Преображенский приказ возглавил его сын Юрий, но Петр не мог полностью положиться на его умение и опыт. В конце 1717 г. было создано несколько розыскных канцелярий под руководством гвардейских офицеров – полковника князя П.М. Гагарина, майоров князя С.А. Салтыкова, М.Я. Волкова, И. Дмитриева-Мамонова, Г.Д. Юсупова, капитана Г.И. Кошелева.

Вскоре несколько временных канцелярий вошли в один постоянный орган – Тайную розыскных дел канцелярию. Возникновение этого учреждения было связано со следствием над наследником престола царевичем Алексеем. Царь Петр давно испытывал беспокойство по поводу сына от первого брака. Царевич и его мать, Евдокия Лопухина, заточенная в суздальский монастырь, представляли потенциальную угрозу для новой семьи царя. Но главное – у Петра и его сподвижников не было уверенности, что Алексей продолжит отцовские преобразования. Наследника ждал монашеский клобук, но он бежал за границу. По приказу Петра царевича Алексея искали по всей Европе. Наконец, он был обнаружен на острове близ Неаполя, где его укрывало австрийское правительство.

Выманить «зверя», как выражалось окружение Петра, было поручено Петру Андреевичу Толстому. Жизненный путь этого представителя дворянского рода начался с крупной неудачи. Как родственник царевны Софьи и участник Стрелецкого бунта, приведшего ее к власти, он попал в немилость сразу же после падения регентши. Однако Толстой умилостивил царя тем, что откликнулся на одно из его начинаний. Нуждаясь в европейски образованных помощниках, Петр посылал дворянских недорослей на учебу за границу. По старым московским понятиям, жизнь среди «богопротивных еретиков» считалась незаслуженным наказанием, которого старались избежать под любым предлогом. Пятидесятидвухлетний Толстой добровольно изъявил желание изучать мореходство и провел два года в Италии. Впрочем, применить свои мореходные познания на деле ему не пришлось.

Нехватка владевших иностранными языками людей заставила Петра переместить Толстого на дипломатическое поприще. Его направили на важный и опасный пост русского посла в Стамбуле. Толстому пришлось познакомиться с местными обычаями. Когда Турция вступила в войну с Россией, его на три года бросили в темницу Семибашенного замка. Стойкость и способности Толстого обеспечили ему расположение царя, которое тот выражал в своеобразной форме. Как-то на пиру Петр поцеловал его в голову и добавил: «Голова, голова, кабы ты не была так умна, я давно бы отрубить тебя велел».