Но Мата Хари хочет вернуться в Париж. Поэтому она подаёт прошение на выдачу ей нового голландского паспорта на имя Маргарет Зелле-Маклид. 15 мая 1916 года ей выдают паспорт. Въездную визу во Францию она также получает без проволочек. Однако британское консульство отказывает ей в визе для краткосрочного пребывания в Англии. На запрос нидерландского МИДа Лондон по телеграфу сообщает, что у Форин Офис есть свои причины, по которым допуск в Англию этой дамы нежелателен. Про телеграфный ответ из Лондона ей ничего не говорят. Поэтому она всё-таки решает ехать во Францию, но не через Англию, а через Испанию.
24 мая 1916 года Мата Хари садится в Гааге на пароход «Зеландия» и следует на нём до испанского порта Виго. Неизвестно, встретилась ли она на этот раз в Мадриде с майором Калле. Во всяком случае, 16 июня 1916 года через пограничную станцию Андэй Мата Хари пытается въехать во Францию. Но французские пограничники неожиданно отказываются впустить её. Они говорят, что причина запрета на её въезд во Францию им неизвестна. Тогда она пишет своему старому другу месье Жюлю Камбону, генеральному секретарю французского МИДа, второму человеку в этом министерстве. Но уже на следующий день, даже не успев отправить письмо, она узнаёт, что может беспрепятственно въехать во Францию. Подобное поведение французских властей не насторожило её, и она с радостью отправляется в Париж.
Предполагая остаться во французской столице на довольно длительный срок, Мата Хари снимает квартиру на фешенебельной авеню Анри Мартэн. Она случайно узнаёт, что её друг офицер царской армии штабс-капитан Вадим Маслов проходит курс лечения на курорте Виттель в Вогезах. Этот курорт расположен в запретной фронтовой зоне, поэтому Мата Хари пытается через лейтенанта Жана Аллора из военного министерства получить специальный пропуск, дающий право на въезд туда. Лейтенант посоветовал ей обратиться к его другу в военное бюро по делам иностранцев.
Далее следует весьма знаменательное событие. Неизвестно, то ли по чистой случайности, то ли французы намеренно дали ей неправильный номер комнаты, то ли она сама поступила так по указанию германской секретной службы, но так или иначе она оказывается лицом к лицу с капитаном Ладу, шефом французской контрразведки. Он расспрашивает Мата Хари об её отношениях с лейтенантом Аллором и штабс-капитаном Масловым. Такой поворот дела был для неё явно неожиданным. Она спросила: «Так вы завели на меня дело?» В ответ Ладу сказал: «Я не верю сообщению англичан, что вы шпионка». Более того, он пообещал помочь получить пропуск в запретную зону. Мата Хари уже собиралась попрощаться, но тут капитан Ладу предлагает ей стать французским агентом и спрашивает, сколько она бы хотела получить за такое сотрудничество. Она просит дать ей время на размышление.