Historien om Uluru, også kalt Ayers Rock, begynte for om lag 550 millioner år siden. Da transporterte elver den sanden som senere ble til Uluru, fra fjellkjeden Petermann Ranges og ut på en slette.
En havstigning om lag 50 millioner år senere oversvømte denne sletten, og trykket fra hav og havsedimenter presset sanden sammen til sandstein.
Enorme sten – af geologer kaldet monolitter – som Uluru findes over hele verden. Lidt uden for Nigerias hovedstad, Abuja, ligger stenen Zuma, som rejser sig 745 meter over omgivelserne og dermed er dobbelt så høj som Uluru.
Den røde fargen kom senere
I forbindelse med tektoniske bevegelser for 400–300 millioner år siden ble hele området løftet opp over havnivå og presset sammen slik at det oppsto fjell og daler. Uluru endte med å stå på høykant.
Siden den gang har vind og vær slitt ned hele området, men fordi Uluru er laget av sandstein, som er hardere enn andre lag i området, rager den i dag 348 meter over resten av Simpsonørkenen.
Sandsteinen er egentlig grålig, men når den kommer i kontakt med luft og fuktighet, ruster jernmineralene den inneholder og får den karakteristiske røde fargen.