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