After the divorce, Margreet was twenty-six years old and back at square one: no husband, no home, and no money. Nevertheless, she was young enough to make a new start, and she did so in a city she had been dreaming about for years - Paris. Later, when an interviewer asked her, 'why Paris?', she answered, 'I don't know. I thought that all women who left her husbands went to Paris.' Her stay in Paris was a failure. In a short time, she returned to the Netherlands with hardly a cent. In 1904, she made a second attempt, and this time she did well. She took dancing lessons, making her debut as 'Lady MacLeod, the oriental dancer' in the salon of Madame Kiréevsky. It was a great success, and more performances in private salons followed. One of the spectators was M. Guimet, the owner of a museum for Asian art in Paris. Very much impressed with her, he invited her to perform in his museum. Not happy with her stage name of Lady MacLeod, however, he thought something better must be found.

On 13 March 1905, the Musée Guimet was the site of the first public performance by the Indian dancer known as Mata Hari. ('Mata Hari' was the name that Margreet and Guimet conceived for the occasion. The words are Malaysian, literally translated as 'eye of the day' but meaning 'sun'.) It marked the beginning of a fascinating career. She received favourable reviews from the press, both in French as well as foreign newspapers. Some journalists were somewhat critical of her dancing technique, but the fact that she danced completely naked was sensational. The world was her oyster. In interviews, the stories she gave about her origins became increasingly fanciful: she had supposedly learned to dance by cunningly penetrating the holy temples of India where the bayaderes danced before the alter of Shiva; her mother was an Indian princess and her father a Scotsman or a baron. It was swallowed lock, stock and barrel. The myth of Mata Hari was born.

On 18 August 1905, she appeared for the first time on the grand stage of the Olympia Theatre. The press was again enthusiastic. After the success at the Olympia, her agent, Gabriel Astruc, arranged for her first performances outside of France. In January 1906, she departed for Madrid where she performed in the 'Central Casino'. Then came a performance at the Monte Carlo Opera in the ballet known as 'Le Roi de Lahore' by Jules Massenet. She was now the highest-paid and most talked-about dancer in Europe.