Маргарета недолго оставалась в Амстердаме, а потом переехала к своему дяде Таконису в Гаагу. Но в Голландии ей трудно было найти работу. А дочку пришлось на время отправить к отцу. И тот уже никогда не вернул ее матери. Но надо признать, что Рудольф Джон был заботливым отцом и предпочитал сам воспитывать дочь, а не платить алименты бывшей жене. Он даже поместил в газете специальное объявление, что не будет платить по долгам жены. И Маргарета решила податься в Париж, тогдашнюю культурную столицу Европы, а то и всего мира, и там попытать счастья.

В Париж наша героиня приехала без единого су и попыталась зарабатывать на жизнь натурщицей. Несколько лет спустя, уже будучи известной актрисой, на вопрос корреспондента, почему она оказалась именно в Париже, она ответила: «Не знаю, но я думаю, что всех жен, сбежавших от мужей, тянет в Париж». Натурщиц в Париже был переизбыток, и платили им мало. К тому же Маргарета потерпела неудачу из-за слишком маленькой груди. Разочарованная, она вернулась в Голландию. Неделю она прожила у дяди своего мужа в Нимвегене, но Рудольф Джон тут же выразил возмущение по этому поводу. И дядя попросил Маргарету убраться подобру-поздорову. И тогда она решила вновь отправиться в Париж. Как она сама говорила репортерам год спустя, «у меня в кошельке было полфранка, и я сразу пошла в Гранд-Отель». Еще она утверждала, что «не было никого, кто бы мне помог». Выбор Маргареты пал на театр «Фоли Бержер», где всегда требовались красивые танцовщицы. Она еще никогда в жизни не танцевала на сцене, но решила попробовать. На Яве она изучала индонезийские традиции и танцевала в местной танцевальной группе. В 1897 году в одном из писем она впервые упомянула свой артистический псевдоним – Мата Хари, который по-малайски означает «солнце» (дословно – «глаз дня»).

Тут на ее пути оказался Молье, владелец знаменитой школы верховой езды на Рю Бенувилль и знаменитого цирка, который носил его имя. Он и сам был прекрасным наездником. Сначала Маргарета выступала как цирковая наездница под псевдонимом «леди Греша Маклеод». Хорошо ездить верхом она научилась еще в Голландской Восточной Индии. Молье был уверен, что такое тело, как у нее, в танцах использовать куда плодотворнее, чем в выездке. Но в тот момент танцевальный опыт Маргареты исчерпывался вальсами и кадрилями, которые она танцевала в восточно-индийских клубах, и уроками танцев в детстве, в родном Леувардене. В годы Первой мировой войны Маргарета говорила одному из своих друзей в Гааге, голландскому художнику Питу ван дер Хему: «Я никогда не умела хорошо танцевать. Люди приходили посмотреть на мои выступления только потому, что я осмелилась показать себя на публике без одежды». К тому времени она уже вполне оценила страшную силу своей красоты. И хорошо знала, как нравиться мужчинам. Она довольно хорошо говорила на малайском языке и видела на Яве и Суматре туземные танцы. И, разумеется, Маргарета никогда не изучала никаких танцев в буддийских храмах на Дальнем Востоке. Она распространяла эту легенду для привлечения публики. И в Париже был спрос на такое искусство, где важнее было тело танцовщицы, а не ее владение техникой танца.

Но только в 1905 году она нашла свой стиль, который принес ей славу. Директор цирка посоветовал ей воспользоваться своей красотой и попытать счастья в роли исполнительницы восточных танцев. Под псевдонимом Мата Хари она стала выступать как восточная танцовщица. Маргарета хорошо знала как малайский язык, так и танцы, которым обучилась в период пребывания в Голландской Восточной Индии. Дебют в новом амплуа состоялся в конце января 1905 года на благотворительном вечере в салоне русской певицы Лидии Киреевской и имел колоссальный успех. Некоторые ее танцы представляли собой нечто близкое к современному стриптизу. В конце номера, исполнявшегося на сцене, усыпанной лепестками роз, танцовщица оставалась полностью обнаженной, утверждая, что «так было угодно Шиве». Уже 4 февраля 1905 года английский еженедельник «Кинг» опубликовал о ней восторженную статью, автор которой утверждал, что «собрал слухи о женщине с Дальнего Востока, приехавшей в драгоценностях и духах в Европу, чтобы внести струю богатства восточных красок и восточной жизни в пресыщенное общество европейских городов». Те же слухи сообщали о сценических представлениях, на которых «покрывала поднимаются и падают». Репортер считал, что представление вроде этого в частном салоне было в самом крайнем случае «лишь с дымкой непристойности».

После ряда представлений в других парижских салонах Маргарета в начале февраля танцевала на 45-м празднике «Dineur de Faveur» (Общества благотворительных обедов). Тогда она еще именовалась леди Маклеод. Мата Хари появилась чуть позже.

Сущность «танца рождения зари» заключалась в том, что баядерка во время танца постепенно раздевалась, оказываясь под конец совершенно голой, – так, по ее сведениям, было угодно Шиве. Мата Хари танцевала при свечах, на полу, засыпанном лепестками роз. Успех был необычайный. Весь Париж заговорил о восточной танцовщице, и она мгновенно вошла в моду. Дочь голландского лавочника оказалась «воплощением таинственного Востока». Один из восторженных рецензентов писал: «Ей известны все добродетели Вишну, все дела Шивы, все свойства Брахмы. С колдовскими чарами баядерки она сочетает богословскую эрудицию брахмана!».

Сама Мата Хари настаивала, что еще с детства знает «священные танцы Востока». Она потчевала доверчивую публику баснями о том, будто она – восточная принцесса (вариант – дочь короля Эдуарда VII и индийской княжны), что у нее есть конь, который позволяет ездить на себе только своей хозяйке, что она воспитывалась на Востоке в монастыре и др. Газета «Курьер франсэ» писала, что, даже оставаясь неподвижной, она околдовывает зрителя, а уж когда танцует, ее чары действуют магически. И она же отмечала, что «эта неизвестная танцовщица из далеких стран – необычная личность. Когда она не движется, она завораживает, а когда танцует – ее обволакивает еще большая таинственность».

На представлении у Киреевской новой танцовщицей всерьез заинтересовался крупный бизнесмен и меценат Эмиль Гиме. Он был также коллекционером и считался экспертом по восточным делам. Он построил музей восточного искусства на площади Иены в Париже, чтобы разместить там свою огромную коллекцию живописи и скульптуры, и решил пригласить своих друзей на настоящий восточный танец. Гиме-то и побудил Маргарету взять псевдоним Мата Хари. Правда, он по наивности думал, что он происходит из языков Индии, а не из малайского языка.

Это была, признаем, по тем временам экстравагантная идея: выступление «яванской танцовщицы» среди экспозиции музея. Мата Хари появилась перед зрителями в роскошном восточном одеянии, взятом из коллекции месье Гиме, но во время танца постепенно сбросила с себя одежду, оставив лишь нитки жемчуга и сверкающие браслеты. На представлении присутствовал весь парижский высший свет. Успех был необычайный, и вскоре слава Маты Хари вышла далеко за пределы Франции.

13 марта 1905 года стал поворотным днем в артистической карьере Маргареты Маклеод. До приезда в Париж она лишь однажды выступала на сцене. В клубном спектакле в Маланге на Яве в 1899 году она сыграла королеву в музыкальной постановке пьесы «Крестоносцы». И тогда в местной газете отмечали, что «зрителям было трудно не восхититься этой элегантной актрисой-любительницей». Теперь же она покорила Париж.