22 ноября 1907 года Рудольф женился на Элизабет Марии Кристине ван дер Маст. Она была на двадцать восемь лет моложе своего мужа и родила ему дочь Норму. Пенсии не хватало, и Маклеод подрабатывал судебными репортажами в ежедневной газете в Арнеме. Он передал дочь Маты Хари на воспитание другой семье. По субботам и воскресеньям она, правда, приезжала к нему домой, чтобы немного побыть у отца. Но новый брак Рудольфа тоже не сложился. Маклеод и Элизабет разошлись в 1912 году, а пять лет спустя последовал их официальный окончательный развод.
В январе 1906 года Мата Хари получила двухнедельный ангажемент в Мадриде. Это было ее первое выступление за пределами Франции. Она танцевала в центральном зале Мадрида. Зрители сожалели, что Мата Хари танцевала в трико, хотя и в «минимально возможном». Мэтр Клюне дал ей письмо своему другу – французскому послу в Мадриде Жюлю Камбону, сделавшему впоследствии удачную дипломатическую карьеру. В Мадриде Мата Хари неожиданно получила письмо от Астрюка. Он сообщил, что вместе со своим другом Раулем Гюнсбургом, директором оперы в Монте-Карло, ранее работавшим в театрах Москвы и Санкт-Петербурга, подписал для нее контракт. Мата Хари должна была выступить в балете Жюля Массене «Король Лахора». Она в ответ попросила прислать ей партитуру балета.
Постановка «Короля Лахора» осуществлялась под патронажем принца Монако Альберта I. Премьера балета прошла с огромным успехом. Теперь Мата Хари получила работу в настоящем театре. Наконец-то признали, что она могла хорошо танцевать. Рецензенты утверждали, что Мата Хари стала «соблазняющей звездой», придав балету «волнующий шарм необычных танцев», и что на карнавале в Ницце она очень эффектно исполнила роль Венеры. Сам Пуччини, находясь в Монте-Карло, прислал ей цветы. А шестидесятичетырехлетний Массне писал ей: «Я был счастлив видеть, как вы танцуете. Примите мои самые искренние поздравления».
Их отношения продолжились. Композитор даже подумывал написать балет специально для Маты Хари. А когда она жила в Берлине, Массне, незадолго до своего возвращения в Париж, восторженно писал ей: ««Как счастлив я был увидеть вас снова! Мата, Мата – через несколько минут я уезжаю в Париж! Спасибо, спасибо – и мое горячее восхищение!».
В августе 1906 года Мата Хари впервые посетила Берлин, где стала любовницей крупного землевладельца Альфреда фон Киперта, лейтенанта 11-го Вестфальского гусарского полка. У Киперта была жена, красавица-венгерка, но роману с Матой Хари это ничуть не мешало, благо средства позволяли Киперту достойно содержать и жену, и любовницу. Для Маты Хари он снял апартаменты на Находштрассе, 39, недалеко от Курфюрстендамм. Они вместе ездили в Силезию, где с 9-го по 12 сентября прошли маневры германской армии. В дальнейшем во французском суде этот факт использовали как доказательство ее шпионской деятельности.
29 августа 1906 года Мата Хари написала из Берлина в Париж Габриэлю Астрюку, что получила из Лондона предложение выступить там в пантомиме, что ей «очень подходит». Но куда охотнее она занималась бы этим в Монте-Карло, где у нее «был такой большой успех». Она также сообщила, что Массне «ввел ее в Венскую оперу».
А уже в конце 1906 года Мата Хари с успехом танцевала в венском Сецессионс-зале, а затем в театре «Аполлон». Поскольку Австро-Венгрия, в отличие от сугубо светской Франции, была страной католической, танцовщица вынуждена была надевать облегающее трико, а не обнажаться полностью. На своих первых выступлениях она танцевала голой. Потом, в театре «Аполло», надела трико.
В Вене Мата Хари жила в отеле «Бристоль». В отеле «Националь» поселилась американская танцовщица Мод Аллан. Между ними сняла апартаменты сама Айседора Дункан. Мод Аллан не надевала на сцену ничего, кроме золотых украшений. Потом на венских сценах появилась еще одна танцовщица, одетая только в носовой платок, «который держала в руке». Но когда прибыла Мата Хари, она выиграла соревнование. Некоторые дамы из высшего общества считали, «что это заходит уже слишком далеко», но после нескольких ее выступлений голоса критиков смолкли. Корреспондент венской газеты «Фремденблатт» так описал Мату Хари в отеле «Бристоль»:
«Высокая и стройная, с пластичностью грации хищного зверя, с иссиня-черными волосами, окаймляющими маленькое лицо, казавшееся необычным… Классические лоб и нос заставляют вспомнить об античности. Длинные черные ресницы оттеняют глаза, а тонкие брови словно написаны кистью художника».