Однако Франсуа де Нион, писавший для аргентинской газеты «Ла Пренса» (Буэнос-Айрес) и испанской «Диарио» (Кадис), усомнился в биографии и таланте Маты Хари и решил побеседовать с человеком, который много лет провел в Индии и которого он назвал «настоящим востоковедом». Анонимный специалист объяснил, что танцовщицы там никогда не выступают голыми, но всегда укутаны в белые покрывала. Тогда Нион публично задался вопросом: «Неужели мы все еще живем во времена Людовика XVI, который однажды устроил роскошный королевский прием одному иностранному послу, который, как выяснилось впоследствии, был простым лавочником из Марселя?».

Тем временем пожилой адвокат Эдуард Клюне, которому еще предстояло сыграть важную роль в жизни Маты Хари, порекомендовал ее знаменитому импресарио Парижа Габриэлю Астрюку. До самого конца тот оставался ее импресарио и агентом. Астрюк сделал ей ангажемент в театре «Олимпия» на бульваре Капуцинов. Поль Рюэ, директор театра, приглашал к себе только самых популярных артистов и хотел сделать «Олимпию» лучшим варьете в мире. Мате Хари за дебют заплатили огромный для того времени гонорар в десять тысяч франков.

Один из своих величайших триумфов она испытала в августе 1905 года в прославленном театре «Олимпия». 2 мая 1905 года ее отметил парижский выпуск «Нью-Йорк Геральд»: «Невозможно себе представить более благородную постановку индийской религиозной мистерии, чем это было сделано здесь».

Ее выступление в спектакле Райнана и Хаудена «Мечта» на музыку Джорджа Бинга в «Олимпии» произвело настоящий фурор. 18 августа 1905 года Мата Хари во время генеральной репетиции впервые выступила в «Олимпии». А через два дня состоялось ее первое выступление перед зрителями. Это был подлинный триумф.

Мата Хари потратила больше денег, чем она заработала, за первые шесть месяцев своего успеха в Париже. Так было и в дальнейшем. Как только она стала получать большие гонорары, один парижский ювелир потребовал конфисковать ее имущество как компенсацию за неоплаченные счета на общую сумму 12 тысяч золотых франков.

Когда это дело разбиралось в суде, Мата Хари вспомнила о своем муже в Голландии и заявила, что все покупки у ювелира «совершались без разрешения моего супруга, голландского офицера». Решение судьи удовлетворило обе стороны. Мата Хари сохранила драгоценности, выплачивая долг по две тысячи франков в месяц.

Тем временем муж танцовщицы потребовал полного официального развода. А для этого необходимо было согласие Маргареты. Но она проявила строптивость. В конце концов Рудольф Джон прислал в Париж своего адвоката Хейманса, чтобы уговорить Маргарету. Джон хотел вступить в новый брак и дать Нон новую мать. Однако Мата Хари умело уходила от темы развода, утверждая, что ей так приятно снова поговорить по-голландски, и просила Хейманса не портить ей минуты удовольствия такой неприятной темой, как развод. Тогда адвокат предъявил ей фотографию голой Маты Хари, утверждая, что это снимок одного из друзей Джона, сделанный в Париже. Смутить такой ерундой танцовщицу, казалось, было трудно. Но она была удивлена и возмущена, так как фотографию сделал один из близких друзей и совсем не для распространения. Хейманс возразил, что любой голландский судья, увидев это, сочтет, что честная женщина и мать «не позволит сфотографировать себя в голом виде даже другу» и что так поступают только проститутки. Мата Хари понимала, что скандал самым неблагоприятным образом скажется и на ее артистической карьере, и на судьбе дочери. И скрепя сердце согласилась на официальный развод. Супруги были окончательно разведены судом в Амстердаме 26 апреля 1906 года.