Паткуль добрался до Москвы лишь в начале апреля. В Москве, к своему большому разочарованию, он узнал, что его друг датский посол П. Хейнс по просьбе Петра отъехал для консультаций в Данию. Паткуль рассчитывал, что датчанин поможет ему сориентироваться в чужой столице, которую он совершенно не знал. К тому же сразу возникали проблемы в общении с москвичами, а беседы через переводчика лишали Паткуля возможности напрямую использовать своё главное оружие – личный шарм. Но нужно было привыкать и к этому, к тому же Паткуль не рассчитывал надолго задерживаться в России, а хотел, получив от царя какое-нибудь важное задание, вернуться в Европу.
Сразу по приезде Паткуль был представлен царю, но не в официальных апартаментах, а в доме у А. Меньшикова. Приём был неформальным и дружеским – ведь Пётр и Паткуль до этого уже встречались дважды. Беседу, вероятно, переводил П. Шафиров. Посланник Пруссии в Москве Й. Г.Кайзерлинг некоторое время спустя докладывал в Берлин, что
К сожалению, следов пребывания Паткуля в Москве сохранилось мало. Что он делал в Москве, какие впечатления получил от новой жизни, с кем общался в свободное время, мы не знаем. Да и было ли у него свободное время? Судя по всему, Паткуль общался в основном с помощниками царя Петра – в первую очередь с канцлером Ф.А.Головиным и с некоторыми иностранными послами в России. Как и ожидалось, Пётр поручил ему важный и трудный участок работы – содействие в реформе армии. Возможно, что Паткуль на первых порах был несколько разочарован – ведь он считал себя в первую очередь политиком. Но нельзя забывать, что армейские проблемы волновали тогда царя в первую очередь, а он знал, что Паткуль в своё время служил в шведской армии, и его советы были весьма и весьма ценными.
О. Шёгрен преувеличивает, приписывая Паткулю всю заслугу в том, что армия Петра полностью была реформирована на шведский образец. Паткуль пробыл в России не так уж много времени, чтобы в одиночку справиться с этой грандиозной задачей. Но известно, что за выполнение поручения Петра он взялся с большим прилежанием и со всей тщательностью своего характера.
Пётр предложил Паткулю написать записку, в которой тот должен был сообщить о своих познаниях и опыте. Записка сохранилась в государственном архиве России, и мы имеем полное представление о том, что изложил в ней наш лифляндец. Паткуль не стал подлаживаться под знатока любимого детища Петра – флота – и прямо написал, что в этом деле он ничего не понимает. Немного он смыслил и в артиллерии и кавалерии. Зато он мог бы оказаться полезным по пехотной части, а также разбирался в математике, в крепостном и инженерном деле. Далее он развивает идею о реорганизации русской армии и высказывает конкретные соображения: российское войско никогда не придёт в совершенство, если не обзаведётся хорошими офицерами. Это главное. На первых порах нужно приобрести знающих и толковых генералов, они, по мнению Паткуля, должны подобрать к себе в дивизии и полки толковых полковников, а полковники уже должны отобрать себе средних и младших офицеров. Главный источник пополнения офицерского корпуса русской армии Паткуль видит в загранице. В конце он пишет, что никакого титула от царя не требует, но если Пётр будет на этом настаивать, то он хотел бы получить звание генерал-лейтенанта и директора всех крепостей России. Что касается денежного содержания, то он удовлетворится суммой, которую получал в Польше у Августа – 8 тысяч талеров.
Царь внял соображениям Паткуля и задумал широкую программу вербовки в Европе высших армейских офицеров, для управления делами которых создавался т.н. кригсрат – военный совет. Паткуль должен был выполнять функцию главного военного комиссара Петра в Европе и отвечать за вербовку и направление в Россию военных специалистов.