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