После окончания женевского коллегиума Лефорта-младшего отправили учиться к одному из марсельских купцов, но вместо этого он вопреки воле отца поступил на службу в крепость Марселя, а потом познакомился с сыном курляндского герцога Карлом-Яковом, который находился в Женеве с деловым визитом и предложил Лефорту-младшему вместе с ним поступить на военную службу в Голландии. Когда же отец Франца умер, не оставив сыну наследства, тому подвернулось новое предложение — подполковник Яков фон Фростен набирал добровольцев для службы в России. Однако наемники попали в Москву в неудачное время — царь Алексей умер, на престол вступил больной царь Федор, и ему на первых порах было не до новых войск, но возвращаться домой не на что. Франц поселился в Немецкой слободе, начал заводить нужные знакомства, и вскоре женился на Елизавете Сугэ — родственнице влиятельного офицера и дипломата Патрика Гордона.

В 1678 г. его принимают на военную службу в чине капитана, а вскоре он получил должность командира роты в Киеве в составе корпуса князя Василия Голицына, «правой руки» царевны Софьи, командовать войсками Киевского гарнизона назначен Патрик Гордон.

Вернувшись в Москву, Лефорт быстро продвигается по службе, всего за несколько месяцев пройдя путь от капитана до подполковника. Тогда же он знакомится с юным Петром. Веселый, щедрый, лихой женевец, да еще и профессиональный военный, успевший «понюхать пороху», — именно таких людей молодой царь хотел иметь в своем окружении. Лефорт же, безусловно, понимал, насколько выгодна ему эта дружба. И он поспешил привязать своего юного друга еще сильнее — помогая тому вступить в переписку с магистратами Женевы и одновременно познакомив его с хорошенькой Анной Монс.

Князь Ф.А. Куракин, краевед и историк XIX в., пишет: «Помянутый Лефорт был человек забавный и роскошный или назвать дебошан французский. Днем и ночью он предавался удовольствиям, обедам, балам. И тут, в его доме первое начало учинилось, что Его Величество научился с дамами иноземными обходиться, и амур начал первый быть одной дочери купеческой, названной Анна Ивановна Монсова. Правда девица была изрядная и умная. Тут же в доме Лефорта началось дебошанство, пьянство такое великое, что невозможно описать, и что многим случалось оттого умирать. <…> Помянутой же Лефорт с того времени пришел до такого градусу, что учинен был генералом от инфантерии, и потом адмиралом, и от пьянства скончался».

Ф. Лефорт

По мнению историка Евгения Анисомова, знакомство с красавицей Анной «облегчило Петру (предки которого мыли руки из серебряного кувшина после церемонии “допущения к руке” иностранных послов) преодоление невидимого, но прочного психологического барьера, разделявшего два чуждых друг другу мира: православной Руси и “богопротивной” Европы, которые и ныне преодолеть не легко».

Анне же это знакомство помогло, в свою очередь, преодолеть бедность (после смерти отца вдове за долги пришлось отдать мельницу и лавку, ей остались только дом с «аустерией» — гостиницей), а потом преодолеть границы Немецкой слободы, если не для себя, то, по крайней мере, для своей семьи.

Петр дарит ей богатые подарки (миниатюрный портрет государя, украшенный алмазами на сумму в 1 тыс. руб.), строит на казенные деньги каменный дом в два этажа и восемь окон; платит Анне и ее матери ежегодный пансион в 708 руб., а в январе 1703 г. пожаловал ей в качестве вотчины Дудинскую волость в Козельском уезде с деревнями (295 дворов).

Расставшись с Евдокией, он открыто живет с Анной и злые языки прозвали ее Кукуйской царицей. Однако и Анна продержалась в фаворитках недолго — Петр заподозрил девушку в неверности и прогнал ее с позором. А вот Лефорт остался среди ближайших друзей царя, получил командование первым отборным полком и произведен в генерал-майоры, а позднее — в полные генералы.