Здесь Франц познакомился с итальянским негоциантом Гуаскони, часто наведывавшимся в Архангельск по торговым делам. Войдя в нелегкое положение молодого военного, он одолжил ему немного денег на питание и иные надобности. Когда получили официальное разрешение от царя, тот же Гуаскони ссудил Лефорту еще шестьдесят талеров на дорогу (путь до Москвы иноземцы должны были оплачивать сами).
19 января 1676 года группа военных во главе с ван Фростеном отбыла из Архангельска в Москву. Весь путь занял чуть больше месяца, а в Белокаменной их ждали большие перемены. Скончался царь Алексей Михайлович, и на российский престол взошел его сын от первой жены Марии Ильиничны Милославской – Федор Алексеевич Романов. 26 февраля 1676 года Лефорт с товарищами прибыли в Посольский приказ, где их поименно занесли в книгу заезжих иностранцев. 30 марта группа в полном составе удостоилась аудиенции у государя. После недолгой беседы царь отпустил всех по местам проживания дожидаться окончательного решения. Четвертого апреля государев вердикт о непригодности всех до одного к воинской службе в рядах российской армии буквально шокировал иностранцев, обнадеженных ван Фростеном и потому уверенных в благополучном исходе дела. Тем же указом не прошедшим отбор кандидатам предписывалось в кратчайшие сроки покинуть пределы России.
Удрученные неожиданным печальным известием военные, тем не менее, не собирались так скоро покидать Московию. Не рассчитывая более на протекцию ван Фростена, каждый решил попытать счастья в одиночку.
Следуя царскому указу от 4 октября 1652 года, обязывавшему иностранцев, не принявших православие, селиться в иноверческом поселении за чертой города, истовый кальвинист Лефорт обосновался в Немецкой слободе, расположенной на правом берегу Яузы близ дворцового села Покровского. Там он снова встретил Гуаскони и был им представлен двум влиятельным персонам – полковнику Полю Менезесу и Патрику Гордону, надеясь на протекцию с их стороны.
Вскоре Франц устроился на должность секретаря к датскому резиденту Магнусу Гиое, но, когда тот отбыл на родину, вместе с ним не поехал. Некий полковник Крафойрд, состоявший на российской службе, собирался выдать за Франца свою дочь, но идею этого брака отвергло семейство Лефортов. Мать и старший брат настоятельно требовали, чтобы Франц как можно быстрее покинул пределы этой дикой страны. Лефорт и сам уже начал отчаиваться, что сумеет поймать в России птицу-удачу.