В Нимвегене Лефорту подфартило. В июне 1675 года в письме матери он писал: «Здесь находится полковник (Яков фон Фростен. — Н. П.), голландец, служивший во Франции и отправляющийся теперь в Московию. Он предложил мне чин капитана. Через две недели корабли отплывут туда. Все собрались в Амстердаме, потому что полковник имеет до двадцати офицеров, его сопровождавших. Капитан сегодня утром уехал и будет ждать нас в Амстердаме. Я писал господину Туртону, чтобы он осведомился по этому делу, и если найдет, что оно хорошо, то я оставлю у господина Туртона письмо, которое обо всем известит вас. Вы думаете, что это сказка? Нет, подполковник должен всех людей (каких только найдет) привезти к великому князю Московии, у которого армия в 200 тысяч человек. Одним словом, матушка, могу уверить вас, что вы услышите или о моей смерти, или о моем повышении…»
Для отправки в Московию требовались деньги, которых у Франсуа не было. Он умел их тратить, но в свои двадцать лет еще не научился их зарабатывать. На этот раз Франсуа опять выручил Туртон. Он уплатил долг хозяйке квартиры, в которой в Нимвегене проживал Лефорт, а также позаботился об отправке Франсуа в Архангельск, уплатив капитану деньги за проезд. Хозяйка так обрадовалась, что дала денег своему постояльцу на дорогу и даже отправила письмо его матери. «Он всегда вел себя крайне похвально и честно, — писала она о Франсуа, — и это было причиной, что я заботилась о нем, как о родном сыне».
Двадцать шестого июля 1675 года торговые корабли, стоявшие в Амстердаме в ожидании попутного ветра, отправились в Архангельск. Понадобилось шесть недель, чтобы 4 сентября корабль, на котором плыли наемники, бросил якорь в Архангельском порту. Здесь Франсуа Лефорту (или Францу, как его стали называть в России) и его товарищам в полной мере довелось познакомиться с волокитой, царившей в учреждениях Московии.
До сих пор неясно, какую миссию выполнял полковник Яков Фростен и нанимал ли он военных по собственной инициативе или по поручению московских властей. Во всяком случае их появление в Архангельске для местного воеводы Федора Полуектовича Нарышкина оказалось полной неожиданностью, поставившей его в затруднительное положение. Воевода не знал, как ему поступить с новоприбывшими. В Архангельск же вместе с полковником Яковом фон Фростеном прибыли подполковник фон Торнин, майор Франц Шваберг, капитаны Станислав Тшебаковский, Филипп фон Дерфельд, Иван Зенгер, Яков Румер и Франц Лефорт, а также поручики Ян Пузн, Питер Юшим, Оливер Дерпен, Михель Янсен и еще два прапорщика.
Вероятнее всего, испытания, выпавшие на долю иноземцев, стали следствием нерасторопности Иноземского приказа, ведавшего наемниками, — он не удосужился предупредить Нарышкина об ожидаемом приезде гостей. Не исключено также, что обстановка на южной границе России стала спокойной настолько, что отпала надобность в иноземных офицерах, и Иноземский приказ проявил полное равнодушие к судьбе прибывших и счел для себя необязательным проявлять о них заботу
Сам воевода к иностранцам не питал симпатий, и будь его воля, он усадил бы незваных гостей на корабль, отправлявшийся из Архангельска в Амстердам, либо, если они окажут неповиновение, отправил бы всех в Сибирь, в ссылку. Но воевода знал, что царь Алексей Михайлович под влиянием очередного временщика А. С. Матвеева (сменившего Б. И. Морозова) проявляет терпимое отношение к иностранцам. А потому, опасаясь вызвать недовольство в Москве, воевода Нарышкин действовал осмотрительно. Требование прибывших выдать им государево жалованье и немедленно отправить их в Москву воевода удовлетворил лишь частично. Он не рискнул без надлежащего указа отправить четырнадцать иностранных офицеров в Москву, но все же отважился определить им кормовой оклад в сумме полтина на день — сумма смехотворно малая, если учесть, что многие из иноземцев прибыли с семьями. Из этой суммы полковнику было положено восемь копеек в день, а капитану — три копейки.
От каждого прибывшего воевода получил расспросные речи — показания — и отправил их в Посольский приказ боярину Артамону Сергеевичу Матвееву, «а полковника и начальных людей к тебе, великому государю, к Москве без твоего, великого государя, указу отпустить не смели, — писал он, — а велели им побыть у Архангельского города до твоего, великого государя, указу. И твоего, великого государя, жалованья на корм велели им давать, примерясь к прежнему, не по велику».