A área coberta pelo APY representa a porção sul das terras natais de Pitjantjatjara e Yankunytjatjara; a porção norte fica no Território do Norte, nos arredores do Uluṟu-Kata Tjuṯa National Park. Em 1921, a metade ocidental do que hoje é o APY foi transformada na Reserva Aborígene do Noroeste. Esta foi ao lado de outra reserva do outro lado da fronteira no Território do Norte, chamada ReservaPetermann. Ambas as reservas se destinavam a formar um refúgio temporário (lugar seguro) para o povo aborígine. O governo disse que eles poderiam continuar lá seu estilo de vida nômade até que pudessem ser assimilados na sociedade moderna. A metade oriental do que é hoje as terras da APY fazia parte do Campo de Testes Woomera durante as décadas de 1950 e 1960. A fronteira da cordilheira foi mais tarde deslocada para o sul, e a terra foi então arrendada aos criadores de gado.
Em 1966, a Austrália do Sul aprovou o Aboriginal Lands Trust Act. Foi a primeira legislação (lei) na Austrália a reconhecer os direitos de terra dos aborígines e permitir que grupos aborígines recebessem terras com base na forma como haviam vivido lá. Nenhum outro estado ou território decretaria algo semelhante até 10 anos mais tarde. Em 1976, o Conselho Pitjantjatjara fez uma reivindicação formal às terras ao redor da cordilheira Musgrave. Isto foi feito em nome de todos Aṉangu com conexões históricas com a área. O primeiro-ministro Don Dunstan e seu governo propuseram um projeto de lei ao parlamento em 1978, com a intenção de conceder aos Pitjantjatjara direitos sobre suas terras. No entanto, os mineiros de opalas se opuseram fortemente à proposta. Eles tinham criado campos de mineração em Mintabie, dentro da área que seria dada ao Aṉangu. O governo mudou após as eleições estaduais de 1979. O novo governo de David Tonkin teve anos de negociações com o Conselho de Pitjantjatjara e os mineiros da Mintabie. Um comitê parlamentar produziu uma decisão final em 2 de março de 1981. Ele disse que a área Mintabie deveria ser incluída na concessão de terras, mas ser arrendada de volta ao governo para que a mineração pudesse continuar lá. O projeto de lei foi aprovado pelo parlamento no mesmo dia.
Tonkin assinou a Pitjantjatjara Land Rights Act em 2 de outubro de 1981, pondo em vigor o projeto de lei. O título de propriedade da terra foi dado aos povos Pitjantjatjara, Yankunytjatjara e Ngaanyatjarra, que formaram um conselho como o governo local. A concessão incluiu as antigas áreas arrendadas na porção oriental: Everard Park, Kenmore Park e Granite Downs. Uma porção do sudeste das terras APY (cerca de 4.500 km2 ou 1.700 sq mi) ainda se sobrepõe ao Woomera Test Range.
O aluguel da Mintabie durou 21 anos, expirando em 2002. A nova legislação em 2009 permitiu outro contrato de arrendamento, que foi assinado em abril de 2012.
