Перед разведчиком вновь встал вопрос о легализации. Было решено, что, пока Лиза будет завершать дела в Копенгагене, Василий пройдет «стажировку» на юге Франции, «акклиматизируется» и присмотрится к новой обстановке. В страну они могли въехать по туристической визе сроком на два месяца, в течение которого им предстояло найти подходящее занятие, дающее право на длительное пребывание во Франции.
По тому же чешскому паспорту на имя Кочека В. Зарубин въехал сначала в Швейцарию, где остановился в скромном пансионе, завел ряд полезных знакомств. Убедившись, что обстановка вокруг него остается нормальной, он затем прибыл в небольшой курортный городок Антиб на юге Франции. Поселившись в пансионе, он получил французские водительские права и вскоре за небольшую сумму приобрел подержанную автомашину престижной марки.
На Лазурном берегу Василий познакомился с молодой француженкой по имени Майя, студенткой Сорбонны. Выяснилось, что ее родители некогда проживали в России, но за участие в революции 1905 года были высланы во Францию. Майя собиралась домой и, узнав, что Зарубин намеревается переехать в Париж, дала ему свой адрес.
Вскоре к Василию в Антиб из Дании приехала Лиза, и они вместе направились в Париж, где остановились в небольшой гостинице. Спустя некоторое время Василий навестил Майю и познакомился с ее родителями, которые не скрывали своих революционных взглядов и симпатий к советской России. В дальнейшем родители Майи были привлечены к секретному сотрудничеству с советской нелегальной разведкой в качестве содержателей конспиративной квартиры, явки и фотолаборатории. Сотрудничать с советской разведкой стали также Майя и ее брат. Один раз Майя даже возила срочную почту в Москву, неоднократно ездила за почтой в гитлеровскую Германию. Ее брат заводил знакомства с офицерами-спортсменами, от которых получал интересную информацию. Во время Гражданской войны в Испании он воевал в интербригаде. В годы Второй мировой войны командовал крупным партизанским отрядом во французском движении Сопротивления и закончил военную службу в чине полковника. Разведывательная работа этой группы агентов продолжалась более 20 лет.
После прибытия в Париж супругам Зарубиным предстояло легализоваться во Франции, для чего было необходимо выбрать соответствующее место для постоянного проживания. Их выбор пал на живописный городок Сен-Клу в предместье Парижа. Здесь они сняли небольшой меблированный домик, стоявший на горе, а машину держали в коммерческом гараже, владельцем которого был француз лет сорока. Однажды, когда Василий по договоренности с владельцем гаража ремонтировал свою машину, француз, наблюдавший за его работой, предложил ему войти с ним в пай, чтобы расширить дело. Василий обещал подумать, отметив, что у него нет разрешения на постоянное проживание в стране. Француз заметил, что это не проблема, поскольку у него хорошие связи в местной полиции и он запросто уладит этот вопрос.
Спустя некоторое время супруги Зарубины получили в местной мэрии постоянный вид на жительство во Франции и стали компаньонами владельца автомобильного гаража. В дальнейшем он свел Василия и Лизу со своими многочисленными знакомыми, принадлежавшими в основном к мелкой буржуазии. Обрастание нейтральными связями способствовало легализации разведчиков в стране. Однако необходимо было приступать к организации нелегальной резидентуры во Франции. Для этого разведчикам-нелегалам следовало решить вопрос о переезде в Париж. А это означало, что Василию нужно было подобрать нового хорошего компаньона, с помощью которого можно было бы вести все коммерческие дела уже в Париже.
Выбор Василия пал на некогда завербованного им еще во Владивостоке агента-поляка под псевдонимом «Башмачник», располагавшего широкими связями в коммерческом мире Европы и имевшего родственников во Франции. Центр поддержал предложение резидента, и вскоре «Башмачник» через Москву и Варшаву прибыл в Ниццу для встречи с Зарубиным. По удачному стечению обстоятельств, младший брат «Башмачника» являлся владельцем небольшой рекламной фирмы в Париже. Он как раз подыскивал себе солидного компаньона, который мог бы вложить средства на расширение деятельности фирмы.
«Башмачник» сам вошел в дело, заключив с братом официальный договор, и порекомендовал ему в качестве компаньона Зарубина. Брат «Башмачника» с удовольствием взял разведчика в долю, заключив с ним формальное соглашение. Вскоре Зарубины перебрались в Париж, где Василий, имея документы на имя совладельца рекламной фирмы, легко оформил постоянный вид на жительство для себя и жены.
В Париже Василий Михайлович и Елизавета Юльевна прожили четыре года. Там же у супругов родился сын Петр. В течение этого времени они не порывали связи с владельцем гаража в Сен-Клу, который вместе с семьей часто навещал их в Париже и все время лестно отзывался о них в кругу своих знакомых.