Aufgrund von Nacktaufnahmen, welche sie für einen Bildhauer hatte anfertigen lassen und die aus bislang ungeklärten Gründen an 'Sammler' verkauft und somit öffentlich bekannt wurden, wurde Mata Hari schließlich 1906 'schuldig' geschieden.
Weil MacLeod seinen Unterhaltspflichten nicht nachkam, war Margaretha gezwungen, für ihren Lebensunterhalt selbst zu sorgen. So ging sie zunächst nach Paris, um dort als Mannequin zu arbeiten, was aber nicht klappte. Auch verschiedene Versuche, als Modell für Maler zu arbeiten, schlugen fehl.
Da sie in den Jahren 1903 bis 1905 auf die Idee gekommen war, einen raffinierten Schleiertanz zu kreieren, verstand sie es nun geschickt, Legenden einer indischen Tempeltänzerin in die Welt zu setzen. Für das Paris der Belle Époque war eine indische Bajadere exotisch und geheimnisvoll, vor allem aber unerhört neuartig. Somit war es kein Wunder, dass die Geschichte und der Tanz Mata Haris, die die Kunst der erotischen Entkleidung perfekt beherrschte, das reiche und gelangweilte Publikum ungewöhnlich faszinierten.
So schrieb beispielsweise der Journalist Marcel Lami im 'Courrier français' (11): "Eine große, dunkle Gestalt schwebt herein. Kräftig, braun, heißblütig. Ihr dunkler Teint, ihre vollen Lippen und glänzenden Augen zeugen von weit entfernten Landen, von sengender Sonne und tropischem Regen. Sie wiegt sich unter den Schleiern, die sie zugleich verhüllen und enthüllen. (...) Das Schauspiel lässt sich mit nichts vergleichen, was wir je gesehen haben. Ihre Brüste heben sich schmachtend, die Augen glänzen feucht. Die Hände recken sich und sinken wieder herab, als seien sie erschlafft vor Sonne und Hitze. (...) Ihr weltlicher Tanz ist ein Gebet; die Wollust wird zur Anbetung. Was sie erfleht, können wir nur ahnen. (...) Der schöne Leib fleht, windet sich und gibt sich hin: es ist gleichsam die Auflösung des Begehrens im Begehren."
Margaretha behauptete von nun an, aus Südindien - von der Küste von Malabar - zu stammen. Ihre Familie bestehe aus Mitgliedern der oberen Kaste der Brahmanen und sie sei in einer unterirdischen Halle des Gottes Shiva aufgewachsen, wo man sie von klein auf in rituellen Tempeltänzen unterrichtet habe, die sie dann zu Ehren des Gottes jeden Tag getanzt habe. Darüber hinaus erfand sie eine Geschichte: Ein bildschöner, junger britischer Offizier habe sie bei einem dieser Tänze gesehen, sich unsterblich in sie verliebt, sie entführt und dann geheiratet. Sie habe ihm einen Sohn geboren, den eine Dienerin später grundlos vergiftet habe. Nach indischem Brauch habe sie danach diese Dienerin eigenhändig erdrosselt... (12) Alle diese Legenden wurden erst sehr viel später als Lügengebilde entlarvt; zunächst begann ein einzigartiger Siegeszug als gefeierte und begnadete Tänzerin.
So trat sie auf den Soirées des Bankiers Rothschild auf oder präsentierte sich bei der Theaterschaupielerin Cécile Sorel oder bei Gaston Menier, dem Erben der Schokoladendynastie Menier; pro Abend soll sie damals etwa 10000 französische Francs verdient und in den teuersten Hotels der Stadt logiert haben. Die Szenen, in denen sie nahezu unbekleidet tanzte, waren Sensation und Skandal zugleich.
Obwohl verschiedene Tänzerinnen ihre 'Tempeltänze' nachahmten, hielt das Interesse an Mata Hari ungebrochen an: Große Varietés boten ihr Engagements an, ihr Bild wurde auf Postkarten, Zigarettenschachteln und Keksdosen verewigt und schließlich kam es auch zu Auslandsauftritten - etwa in Spanien, Monaco, Deutschland oder Österreich. Auch in der Alpenrepublik feierte sie Triumphe. So hieß es im 'Neuen Wiener Journal' vom 15. Dezember 1906 unter anderem: "Isadora Duncan ist tot, es lebe Mata Hari! Die Barfußtänzerin ist vieux jeu, die Künstlerin up to date zeigt mehr (...) Unter dem Schleier trägt die schöne Tänzerin auf dem Oberkörper einen Brustschmuck und einen Goldgürtel, sonst nichts. Die Kühnheit des Kostüms bildet eine kleine Sensation. (...) Das, was die Künstlerin im Tanze verrät, ist reinste Kunst (...)."
Als immer mehr Tänzerinnen ihre Tänze kopierten, kam es zwar zu einem Karrierebruch, dennoch blieb sie auch weiterhin ein geschätztes Mitglied der Pariser Gesellschaft und trat immer wieder in privaten Salons der italienischen Oberschicht und diversen Theatern auf. Weil es jedoch immer wieder zu größeren Eklats aufgrund von Mata Haris überzogenen Ansprüchen kam, wandten sich viele Manager und Regisseure enttäuscht von ihr ab.
Etwa um die gleiche Zeit versuchte Mata Hari, Kontakte zu ihrer Tochter Non wiederherzustellen, doch auch damit hatte sie keinen Erfolg. Der Ex-Ehemann sandte alle ihre Briefe ungeöffnet wieder zurück. Als der Erste Weltkrieg ausbrach, verließ sie Deutschland und kehrte nach Den Haag zurück, wo sie zunächst ein kleines Haus mietete (ihren Villenhaushalt in Neuilly bei Paris löste sie gleichzeitig auf).
Weil Mata Hari im Lauf ihrer Karriere als Tänzerin immer wieder einmal mit Persönlichkeiten aus Politik und Gesellschaft Kontakt gehabt hatte, ergab es sich, dass ihr Carl H. Cramer, der deutsche Konsul in Amsterdam, im Frühjahr 1916 ein finanziell verlockendes Angebot machte - wenn sie sich bereit erkläre, 'Deutschland gewisse Informationen zukommen zu lassen' (13).
In einem 14teiligen Erfahrungsbericht des deutschen Generalmajors a.D. Friedrich Gempp über den deutschen militärischen Nachrichtendienst im Ersten Weltkrieg, der etwa um die Mitte der 1970er Jahre aus den USA nach Deutschland gelangte und der inzwischen im Freiburger Militärarchiv einsehbar ist, waren u.a. auch Informationen der Abteilung IIIb über eine gewisse 'Agentin H-21' enthalten, bei der es sich um Mata Hari gehandelt hat.
Aus ihnen geht hervor, dass Mata Hari im Spätherbst 1915 in den Dienst des deutschen Geheimdienstes getreten war. Walter Nicolai, der damalige Chef der Abteilung IIIb, hatte Mata Hari nach Köln kommen lassen, wo beschlossen wurde, sie zur Agentin ausbilden zu lassen. Der ihr zugewiesene Führungsoffizier Major Roepell habe ihr dann auf langen Spaziergängen das Agenten-Einmaleins beigebracht, ein Experte mit ihr 'chemisches Schreiben' geübt. Hauptaufgabe Mata Haris sei es gewesen, die Offensivpläne des Gegners herauszubekommen, Reisen durch militärisch interessante Gebiete Frankreichs zu unternehmen und ständigen Kontakt mit der deutschen Agentenzentrale in Madrid zu halten.
George Ladoux vom Deuxième Bureau, der zweiten Abteilung des französischen Auslandsnachrichtendienstes, wurde bereits um die Mitte des Jahres 1915 auf Mata Hari aufmerksam; zuvor war sie bereits auch dem britischen Secret Intelligence Service aufgefallen. Weil die Verdachtsmomente für eine Festnahme indes nicht ausreichten, stellte Ladoux der Tänzerin im Dezember 1916 bewusst eine Falle. Er ließ ihr die Namen von sechs belgischen Agenten zukommen, die sie demnächst aufsuchen sollte. Fünf dieser sechs Männer wurden verdächtigt, irreführende Meldungen zu liefern, der sechste arbeitete nachweislich für Frankreich und Deutschland. Zwei Wochen nach Abreise Mata Haris wurde dieser Mann von den Deutschen erschossen, während die anderen fünf unbehelligt blieben. Daraus folgerte Ladoux, dass Mata Hari die Namen der Spione den deutschen Militärbehörden verraten haben musste. Als sie aus Spanien wieder nach Frankreich zurückkehrte, wurde sie am Morgen des 13. Februar 1917 von Polizeikommissar Priolet festgenommen und Hauptmann Pierre Bouchardon, dem Untersuchungs- richter des Kriegsgerichts, vorgeführt, anschließend als Untersuchungshäftling in das Frauengefängnis Saint-Lazare verbracht.
Fünf Monate später war die Anklageschrift fertiggestellt; am 24. Juli 1917 begann im Pariser Justizpalast der Prozess unter Vorsitz des Richters Lieutenant-Colonel Albert Ernest Somprou und sechs Beisitzern, der nur eineinhalb Tage dauerte. Auch George Ladoux war anwesend, denn der Richter hatte seine Anwesend für nötig befunden, 'um einzelne Punkte zu klären und bedarfsweise auszusagen'. (14)
Die Verteidigung Mata Haris übernahm der Jurist Eduard Clunet, der bei seiner Verteidigung vor allem auf emotionsgeladene Reden setzte, um die Frau als Opfer der Umstände und eine in finanzielle Not geratene Künstlerin darzustellen. Doch er hatte keinen Erfolg damit, denn das französische Militärgericht befand Mata Hari der Spionage für Deutschland und somit des Hochverrats und der Unterstützung des Feindes für schuldig.
Obwohl es keine eindeutigen Beweise für 'Spionage' gab, wurde Mata Hari am 25. Juli 1917 wegen Doppelspionage und Hochverrats von den Militärrichtern zum Tode verurteilt. Untersuchungsrichter Bouchardon führte zum Beispiel vor Gericht an: "....Sprachkenntnisse, zahllose Verbindungen,