Uluru alkoi muodostua satoja miljoonia vuosia sitten, kun eri maalajit alkoivat kerrostua ja tiivistyä. Prosessin myöstä rakentui hiekkakivimuodostelma, jonka maanpäällinen osa Uluru on. On arveltu, että koko muodostelma olisi sadan kilometrin levyinen ja viiden kilometrin paksuinen, ja että siihen kuuluisi Ulurun lisäksi myös noin kolmenkymmenen kilometrin päässä sijaitseva Katatjuta.[1]

William Gosse oli ensimmäinen eurooppalainen, joka näki Ulurun. Hän oli tutkimassa Australian pohjoisterritorion aavikkoja vuonna 1873 ja nimesi löytämänsä kallion Ayersin kallioksi Australian pääministeri Henry Ayersin mukaan, tietämättä että alkuasukkaat olivat jo antaneet sille nimen Uluru.[2]

Ensimmäiset turistit tulivat Ulurulle 1930-luvulla. Ulurun ja Katatjutan ympärille perustettiin kansallispuisto vuonna 1950. Alkuperäiskansaan kuuluvia oli jo 1930-luvulla kehotettu pysymään poissa alueelta, ja vuoden 1958 jälkeen heiltä kiellettiin kokonaan pääsy kansallispuistoon. Vuonna 1976 toimeenpannun alkuperäiskansojen Maaoikeuslain seurauksena Uluru ja kansallispuisto annettiin alueen alkuperäisten asukkaiden anangujen omistukseen vuonna 1985 sillä ehdolla, että he vuokraavat alueen 99 vuodeksi Australian valtiolle. Nykyisin puistossa vierailee lähes puoli miljoonaa turistia vuosittain. Anangut metsästävät ja keräilevät puiston alueella jonkin verran, mutta turismi työllistää lähes koko yhteisön. Ananguja on turistioppaina sekä kertovat vuoren historiasta ja kulttuuristaan. Puiston pääsymaksuista osa menee ananguyhteisön kehittämiseen.[3]

Uluru-Kata Tjutan kansallispuisto liitettiin Unescon maailmanperintöluettelon vuonna 1987 luonnonarvojensa vuoksi, ja alueen suojelua laajennettiin vuonna 1994 kattamaan sen kulttuuriarvot.[4][5]