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