1876. augusztus 7-én, Hollandiában, a Leeuwarden nevű fríz városban született Margaretha Geertruida Zelle néven. A családban Grietjének szólították. Kalapkereskedő volt az apja. Jól ment nekik. Grietje és testvérei mindent megkaptak, amit egy módos családban megkaphattak. Előkelő iskolába járatták őket.
Ám 1889-ben, amikor Grietje kamaszodni kezdett, az olajüzletben spekuláló papa tönkrement. Szülei elváltak, anyukája hamarosan, 1891-ben meghalt. Apja újra nősült. Grietjét anyai nagyanyja vette magához, majd egyik nagybátyjánál, egyben keresztapjánál helyezték el. Leidenben tanult óvónőnek. Az iskolaigazgató hevesen rányomult, mire keresztapja kivette az iskolából. Hamarosan megszökött tőle, és egy másik nagybátyjához menekült Hágába.
Rudolf MacLeod, a harmincas évei végén járó holland katonatiszt megunta az agglegényéletet és házassági hirdetést adott fel Nieuws van den Dag című lapban, amelyre a 18 éves, ide-oda hányódó leány lelkesen válaszolt. Megismerkedett a nyalka katonatiszttel, elszédítette az egyenruha, a sok kitüntetés, a katonatiszt hódító fellépése, és hamarosan hozzáment feleségül.
Amikor 1895 júliusában egybekeltek, valószínűleg még csak ők tudtak a gyermekről, aki 1896 januárjában megszületett és a Norman nevet kapta. A házasság a társadalom felsőbb rétegébe emelte az ifjú arát. MacLeodot visszavezényelték a holland Kelet-Indiákra (a mai Indonéziába). 1897-ben érkezett a család Jáva szigetére Toempoeng városába. 1898-ban itt született meg Norman lánytestvére, Luisa Jeanne.
Margaretha Geertruide Zelle és Rudolf MacLeod az esküvőjükön
AFP / Collection Roger-Viollet
A családi boldogság nem tartott sokáig. A férj ivott, mint a kefekötő, verte a feleségét, a gyerekeit, ágyast is tartott, ami bevett szokás volt a gyarmatokon.
Amikor MacLeodot átvezényelték Medanba, Szumátra fővárosába, a felesége a gyerekekkel Jáván maradt még egy ideig, és az ottani könyvvizsgáló családjával élt. Ekkortájt írta Hollandiában élő barátainak, hogy felvette a Mata Hari nevet, amely helyi nyelven a nap szemét jelenti.
