At a major ceremony at the park on 26 October 1985, with the deeds of grant under the Land Rights Act delivered by the Governor General, Sir Ninian Stephen. The lease document was signed at the same time by the newly formed Uluru-Kata Tjuta Aboriginal Land Trust and the Director of National Parks. This occasion formally acknowledged Anangu ownership of the park whilst at the same time recognising the value of their land as a park of national and international importance.
The Uluru-Kata Tjuta Board of Management was established under the National Parks and Wildlife Conservation Act 1975 on 10 December 1985 and held its first meeting on 22 April 1986. The Board of Management continues under the Environment Protection and Biodiversity Conservation Act 1999.
Leading up to 1985 were many years of negotiation for Anangu to become the legal owners of their traditional land. They wanted the right to look after the area in what they believed to be the proper way. Anangu became increasingly concerned that their traditional lands were under pressure from pastoralism, mining and tourism.
In 1971 there were meetings held in Ernabella by the Office of Aboriginal Affairs where traditional owners of Uluru expressed their concerns. Paddy Uluru spoke about Uluru and voiced concerns at the desecration of sites by tourists. Senior Aboriginal people asked the Federal Government for help in protecting these sites.
In 1972 traditional owners gathered at Uluru for the first recorded ceremonies emphasising their traditional ownership.
In July 1973 the Federal House of Representatives Standing Committee on Environment and Conservation came to Uluru to prepare a report on the park. They talked with tourist operators and went to Mimili to hold meetings with traditional owners. Paddy Uluru spoke at these meetings and spoke of wanting to return to Uluru to pass on the stories to his children. The report produced by this committee concluded:
'In the future the traditional rights of Aboriginals must be assured and a central role in responsibility for management will rest with them.'
This report recommended that the park be managed by the Federal Parks and Wildlife Service and suggested ways in which Aboriginal people could be involved in Park management. It also suggested creating a suitable living area for Anangu to help facilitate their involvement in the park. These recommendations were carried out and a bore and camp-ground was established.
In 1979, a claim was lodged under the Aboriginal Land Rights (Northern Territory) Act 1976 (the Land Rights Act) by the Central Land Council (on behalf of the traditional owners) for an area of land that included the park. The Aboriginal Land Commissioner, Mr Justice Toohey, found there were traditional owners for the park but that the park could not be claimed as it had ceased to be unalienated Crown land upon its proclamation in 1977. The claimed land to the north east of the park is now Aboriginal Land held by the Katiti Aboriginal Land Trust.
In line with commitments made by the newly elected Commonwealth Government in 1983, the National Parks and Wildlife Conservation Act 1975 and the Land Rights Act were amended in 1985 to provide for the park to be granted as Aboriginal land and to be jointly managed by Anangu and the Commonwealth, through a lease to the Director of National Parks and a joint Board of Management with an Anangu majority. In the negotiation of these arrangements it was agreed between Anangu and the Government that the lease would be for 99 years and that Anangu would receive an annual rent and share of Park revenue.