По окончании инструктажа Мата Хари уехала обратно в Гаагу. Её первым заданием было выяснение в Париже ближайших планов наступления союзников. Кроме того, во время поездки и пребывания в районах, представляющих интерес в военном отношении, она должна была выяснить, где происходят передвижения войск. Её обязали поддерживать постоянную связь с двумя координационными центрами германской разведки против Франции: с центром «Запад» в Дюссельдорфе, руководимым майором фон Репелем, и агентурным центром германского посольства в Мадриде, возглавляемым майором Арнольдом Калле.
Вскоре после возвращения Мата Хари навещает консул Крамер. Позднее, на допросе, она рассказала об этой встрече так, словно она произошла в мае 1916 года, то есть до второй поездки во Францию: «Консулу стало известно, что я запросила въездную визу. Он начал разговор: „Я знаю, вы собираетесь поехать во Францию. Не согласились бы вы оказать нам определённые услуги? Нам бы хотелось, чтобы вы собрали там для нас информацию, которая, на ваш взгляд, могла бы нас заинтересовать. В случае вашего согласия я уполномочен уплатить вам 20000 франков“. Я сказала ему, что сумма довольно скромная. Он согласился и добавил следующее: „Чтобы получить больше, вы должны сначала доказать, на что вы способны“. Я попросила немного времени на раздумье. Когда он ушёл, я подумала о своих дорогих шубах, задержанных немцами в Берлине, и решила, что будет справедливо, если я вытяну из них максимум того, что смогу. Поэтому я написала Крамеру: „Я всё обдумала. Можете принести деньги“. Консул пришёл немедленно и выплатил обещанную сумму во французской валюте. Он сказал, чтобы я писала ему чернилами для тайнописи. Я возразила, что это будет для меня неудобно, поскольку теперь мне придётся подписываться своим настоящим именем. Он ответил, что есть такие чернила, которые никто прочесть не сможет, и добавил, чтобы я подписывала свои письма H-21. Затем он передал мне три небольших флакона, помеченных цифрами 1, 2, 3. Получив от месье Крамера 20000 франков, я вежливо выпроводила его. Уверяю вас, что из Парижа я никогда не написала им и полуслова. Кстати говоря, эти три флакона, вылив их содержимое, я бросила в воду, едва наш пароход подошёл к каналу, идущему из Амстердама в Северное море».
Британские агенты знают о деятельности Крамера в рамках III-b и следят буквально за каждым его шагом. Они сообщили в лондонский центр о визите консула к Мата Хари. В декабре 1915 года она прибывает во Францию. Ей пришлось ехать через Англию, так как Бельгия была оккупирована немцами.
Прибыв в Париж, она снимает номер в «Гранд-отеле» и приступает к выполнению своей миссии. Встречаясь со старыми знакомыми, Мата Хари пытается в светской болтовне узнать у них всевозможную интересную информацию. Среди её друзей и бывший военный министр Адольф Мессими, и лейтенант Жан Аллор, который служит в военном министерстве, наконец, и Жюль Камбон, генеральный секретарь министерства иностранных дел. Ночью она тоже не теряет зря времени, встречаясь со многими французскими и британскими офицерами.
Вскоре у неё складывается довольно полная картина намерений союзников на германском фронте. В конце года она сообщает германскому агенту, что, по крайней мере в ближайшее время французы не планируют наступательных операций. Это донесение подтверждает информацию, полученную из других источников. Поэтому германское командование готовит очередное наступление лишь к началу 1916 года.
Германская секретная служба тем временем начинает дезинформационную операцию. Она распространяет всевозможные слухи и инсценирует передвижения войск, чтобы создать впечатление, будто немцы готовят крупное наступление одновременно в Эльзасе и Фландрии. С помощью этих отвлекающих манёвров руководству германской армии удаётся скрыть подготовку к наступлению на Верден, намеченному на февраль 1916 года.
Из Парижа Мата Хари отправляется в Испанию. Эта поездка носила разведывательный характер — она получила задание провести наблюдения на железнодорожных узлах Центральной и Южной Франции за перемещениями военных эшелонов и за скоплениями войск. 11 января 1916 года Мата Хари достигает франко-испанской, пограничной станции Андэй, а ещё через сутки прибывает в Мадрид. Она останавливается в «Палас-отеле» и связывается с военным атташе германского посольства майором Калле, чтобы передать информацию о том, что видела и слышала во время путешествия. Эта информация, видимо, показалась майору настолько важной, что он распоряжается немедленно передать её консулу Крамеру в Амстердам. Радиограмма, как всегда, шифруется кодом министерства иностранных дел.
Никто не догадывается, что британская служба радиоподслушивания перехватывает его донесение и передаёт его своим агентам. Расшифровка германских радиограмм не представляет для англичан особого труда, поскольку Александр Сцек из немецкого радиоцентра в Брюсселе между ноябрём 1914 года и апрелем 1915 года постепенно переписал и передал британской разведке всю кодовую книгу германского МИДа.
Британская служба МИ-6 может без особых затруднений установить, какой именно агент поехал из Парижа через Андэй в Мадрид, чтобы затем сообщить о своих наблюдениях военному атташе Калле. Перехваченная радиограмма подтверждает выводы, сделанные недавно службой МИ-6, что Мата Хари завербована германской разведкой. После беседы в Мадриде она через Португалию возвращается в Гаагу, где её с нетерпением ожидает старый друг барон ван дер Капеллен.
Но Мата Хари хочет вернуться в Париж. Поэтому она подаёт прошение на выдачу ей нового голландского паспорта на имя Маргарет Зелле-Маклид. 15 мая 1916 года ей выдают паспорт. Въездную визу во Францию она также получает без проволочек. Однако британское консульство отказывает ей в визе для краткосрочного пребывания в Англии. На запрос нидерландского МИДа Лондон по телеграфу сообщает, что у Форин Офис есть свои причины, по которым допуск в Англию этой дамы нежелателен. Про телеграфный ответ из Лондона ей ничего не говорят. Поэтому она всё-таки решает ехать во Францию, но не через Англию, а через Испанию.
24 мая 1916 года Мата Хари садится в Гааге на пароход «Зеландия» и следует на нём до испанского порта Виго. Неизвестно, встретилась ли она на этот раз в Мадриде с майором Калле. Во всяком случае, 16 июня 1916 года через пограничную станцию Андэй Мата Хари пытается въехать во Францию. Но французские пограничники неожиданно отказываются впустить её. Они говорят, что причина запрета на её въезд во Францию им неизвестна. Тогда она пишет своему старому другу месье Жюлю Камбону, генеральному секретарю французского МИДа, второму человеку в этом министерстве. Но уже на следующий день, даже не успев отправить письмо, она узнаёт, что может беспрепятственно въехать во Францию. Подобное поведение французских властей не насторожило её, и она с радостью отправляется в Париж.
Предполагая остаться во французской столице на довольно длительный срок, Мата Хари снимает квартиру на фешенебельной авеню Анри Мартэн. Она случайно узнаёт, что её друг офицер царской армии штабс-капитан Вадим Маслов проходит курс лечения на курорте Виттель в Вогезах. Этот курорт расположен в запретной фронтовой зоне, поэтому Мата Хари пытается через лейтенанта Жана Аллора из военного министерства получить специальный пропуск, дающий право на въезд туда. Лейтенант посоветовал ей обратиться к его другу в военное бюро по делам иностранцев.
Далее следует весьма знаменательное событие. Неизвестно, то ли по чистой случайности, то ли французы намеренно дали ей неправильный номер комнаты, то ли она сама поступила так по указанию германской секретной службы, но так или иначе она оказывается лицом к лицу с капитаном Ладу, шефом французской контрразведки. Он расспрашивает Мата Хари об её отношениях с лейтенантом Аллором и штабс-капитаном Масловым. Такой поворот дела был для неё явно неожиданным. Она спросила: «Так вы завели на меня дело?» В ответ Ладу сказал: «Я не верю сообщению англичан, что вы шпионка». Более того, он пообещал помочь получить пропуск в запретную зону. Мата Хари уже собиралась попрощаться, но тут капитан Ладу предлагает ей стать французским агентом и спрашивает, сколько она бы хотела получить за такое сотрудничество. Она просит дать ей время на размышление.