Восстание декабристов наглядно продемонстрировало неэффективность системы политического сыска Александровской эпохи. Новый император Николай I взамен нее решает создать принципиально новый орган государственной безопасности, в основу которого был положен проект А.Х. Бенкендорфа, поданный императору в январе 1826 г. Однако записка будущего руководителя Третьего отделения решала вопрос в теоретическом плане и почти не касалась конкретных сторон деятельности нового органа. В марте 1826 г. фон Фок направляет А.Х. Бенкендорфу записку относительно «высшей наблюдательной полиции». Автор предлагает для создания полиции «по новому образцу» «на первый случай» перевести шесть ««благонадежных и опытных чиновников из Министерства внутренних дел в разряд «чиновников по особым поручениям», подчинить их непосредственно начальнику Третьего отделения и поручить организацию новой агентурной сети, простимулировав их деятельность высоким годовым жалованьем. Новая структура должна была состоять из нескольких секретарей, служителей, управляющего и полностью подчиняться одному начальнику. На основе объединенных предложений А.Х. Бенкендорфа и М.Я. фон Фока в конечном итоге и создается Третье отделение, куда последний вместе с большинством своих подчиненных и переходит из Министерства внутренних дел.

Один из первых исследователей архивов новой структуры государственной безопасности Б.Л. Модзалевский так характеризует роль бывшего руководителя Особенной канцелярии МВД:

«...душою, главным деятелем и важнейшею пружиною всего сложного полицейского аппарата был неутомимый фон Фок, сосредоточивший в своих опытных руках все нити жандармского сыска и тайной агентуры. Его деятельность была поразительно обширна, он отдавался ей, по-видимому, с любовью, даже со страстью, в буквальном смысле слова не покладая рук... Своим большим образованием и кипучею деятельностью он как бы дополнял Бенкендорфа, человека малообразованного и вялого, ленивого; их отношения друг к другу были самые дружественные, хотя Фок в своих письменных сношениях с «шефом» никогда не терял тона почтительного уважения».

Фон Фок и его опытные подчиненные налаживают агентурную сеть для Третьего отделения, охватывающую все слои общества – от лакеев и извозчиков до генералов и лиц, близко стоящих к трону. Поскольку Николай I и А.Х. Бенкендорф стремились «облагородить» политический сыск и привлечь в его ряды людей, которые с готовностью служили бы за чины, награды и благодарности, чем за денежное вознаграждение, бывший начальник Особенной канцелярии быстро приспосабливается к новым веяниям и в письме от 17 июля 1826 г. характеризует А.Х. Бенкендорфу завербованных им новых агентов:

«Г[осподин] Нефедьев имеет деревню под Москвой... Это очень благоприятно для нашего дела. С этим господином не знаешь никаких затруднений: ни жалованья, ни расходов. Услуги, которые он может оказать нам, будут очень важны вследствие его связей в высшем и среднем обществах Москвы. Это будет ходячая энциклопедия, к которой всегда удобно обращаться за сведениями относительно всего, что касается надзора... Нефедьев – статский советник и имеет орден Св. Владимира 3-го класса, он честолюбив и жаждет почестей... Граф Лев Сологуб... может принести нам большую пользу в Москве... С этим человеком также никакого жалованья, никаких расходов... Предложение его – действовать заодно с «надзором», цель же быть покровительствуемым во всем, что касается ведения интересующего его дела. Граф – человек скромный и способный выполнять даваемые ему поручения».