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