С этим обещанием, однако, расходятся его истинные устремления. Летом 1675 года Лефорт едет в Россию. Он так и не получил обещанной должности в свите герцога. Лефорт расстается с Фридрихом-Казимиром и вскоре знакомится с голландским подполковником ван Фростеном. Ван Фростен набирал отряд офицеров на российскую службу и предложил Лефорту чин капитана. Тот сразу же принял решение: «Через две недели корабли отправляются туда».

Что заставило его отправиться в страну, о которой он мог иметь в лучшем случае весьма смутные представления? Обещанный чин капитана, без сомнения, был очень привлекательным. В Европе получить его так быстро было невозможно: Фридрих-Казимир мог обещать ему всего лишь чин прапорщика. Авантюризм и страстное желание быть отважным воином возобладали над рассудительностью. Автор жизнеописания Лефорта XVIII века И. Голиков пишет об этом шаге: «Воин ищет славы повсюду, где только надеется найти». Вряд ли, конечно, в Голландии было много известно об учреждаемых в России полках «нового строя» и о том, чем они отличаются от старого войска, однако его убедили, что в России европейцам, уже имевшим военный опыт, удастся достигнуть многого.

В конце июля Лефорт уезжает в Россию, не сомневаясь в удаче: «Одним словом, матушка, могу уверить вас, что вы услышите или о моей смерти, или о моем повышении». Через шесть недель этим радужным надеждам, похоже, пришел конец. Иноземцы высадились в Архангельске и столкнулись с русскими порядками.

По установленному порядку архангелогородский воевода Ф. П. Нарышкин принял вновь прибывших иноземцев, назначил им временное содержание и отправил в Москву донесение вместе с «расспросными листами». Вся команда, в том числе и Лефорт, в своих «листах» записала себя в капитаны и уроженцы Данцига. Это, по-видимому, была хитрость, как и то, что все назвались давними «братьями по оружию»: «И от Прусской де земли были они в Ишпанской и Галанской землях и служили от ишпанцев и от галанцов со францужаны на многих боях с полковником Фан Фростеном».

25 августа Нарышкин отослал документы в Москву. Иноземцам был установлен «корм», полтина на всех 14 человек (на долю Лефорта приходилось три копейки), до тех пор, пока Посольский приказ не примет решения. Ответ, причем неблагоприятный для иноземцев, пришел только в ноябре: «Полковника Фан Фростена с товарищи выслать за море, а к Москве не отпускать и корм им прекратить».

Компания составляет челобитную Алексею Михайловичу: «Великий Государь! Дозволь нам приехать к Москве на наших проторех и подводах, а если мы на твою службу годимся, вели, государь, нас принять, а если не годимся, укажи нас в немецкий рубеж отпустить, чтобы нам здесь с женишками и детишками голодною смертию не помереть. Царь-государь, смилуйся!» Алексей Михайлович внял просьбе и 16 декабря распорядился отпустить несчастных к Москве. Положение отряда в Архангельске было незавидным. Лефорт считал, что в этом была вина губернатора, относившегося к ним без всякого сочувствия. По мнению Лефорта, Нарышкин был «хуже черта» и собирался отправить весь отряд не в Москву, а в Сибирь. Впечатления Лефорта об Архангельске остались ужасные: «Не в состоянии описать Вам подробно, – пишет он другу своей семьи голландцу Туртону, – здешнюю жалкую страну и здешний образ жизни. Во Франции был бы в диковинку дом, в котором живем мы». Но все же он не отчаивался и не жалел о том, что приехал. Он вспоминал совет Туртона: «не мешает потерпеть немного». К тому же в Архангельске Лефорт познакомился с итальянским купцом Франческо Гуасконе, который помог ему пережить зиму. 19 января наконец отряд ван Фростена отправился в Москву. По прибытии в столицу офицеры узнали, что Алексея Михайловича уже нет в живых.