L'area coperta dall'APY rappresenta la porzione meridionale delle homelands Pitjantjatjara e Yankunytjatjara; la porzione settentrionale si trova nel Territorio del Nord e circonda il Parco NazionaleUluṟu-KataTjuṯa. Nel 1921, la metà occidentale di quelle che oggi sono le terre dell'APY fu trasformata nella Riserva Aborigena del Nord-Ovest. Questa fu affiancata da un'altra riserva oltre il confine nel Territorio del Nord, chiamata RiservaPetermann. Entrambe le riserve erano destinate a formare un rifugio temporaneo (luogo sicuro) per gli aborigeni. Il governo disse che avrebbero potuto continuare lì il loro stile di vita nomade fino a quando non avrebbero potuto essere assimilati nella società moderna. La metà orientale di quelle che ora sono le terre APY era parte del Woomera Test Range durante gli anni '50 e '60. Il confine del poligono fu poi spostato più a sud, e la terra fu poi affittata agli allevatori di bestiame.
Nel 1966, l'Australia meridionale approvò l'Aboriginal Lands Trust Act. Fu il primo atto legislativo (legge) in Australia a riconoscere i diritti alla terra degli aborigeni e a permettere che ai gruppi aborigeni venisse data la terra in base a come ci avevano vissuto. Nessun altro stato o territorio avrebbe promulgato qualcosa di simile fino a 10 anni dopo. Nel 1976, il Consiglio Pitjantjatjara fece una richiesta formale per le terre intorno ai Musgrave Ranges. Fu fatto a nome di tutti gli Aṉangu con connessioni storiche alla zona. Il premier Don Dunstan e il suo governo proposero un disegno di legge al parlamento nel 1978, con l'intenzione di concedere ai Pitjantjatjara i diritti sulla loro terra. Tuttavia, i minatori di opale si opposero fortemente alla proposta. Avevano allestito campi di estrazione a Mintabie, all'interno dell'area che sarebbe stata data all'Aṉangu. Il governo cambiò dopo le elezioni statali del 1979. Il nuovo governo di David Tonkin ebbe anni di negoziati con il Consiglio Pitjantjatjara e i minatori di Mintabie. Una commissione parlamentare ha prodotto una decisione finale il 2 marzo 1981. Essa disse che l'area di Mintabie doveva essere inclusa nella concessione della terra, ma essere riaffittata al governo in modo che l'attività mineraria potesse continuare lì. Il disegno di legge fu approvato dal parlamento lo stesso giorno.
Tonkin firmò il Pitjantjatjara Land Rights Act il 2 ottobre 1981, mettendo in vigore la legge. Il titolo di proprietà della terra fu dato ai popoli Pitjantjatjara, Yankunytjatjara e Ngaanyatjarra, che formarono un consiglio come governo locale. La concessione includeva le aree precedentemente affittate nella porzione orientale: Everard Park, Kenmore Park e Granite Downs. Una porzione del sud-est delle terre APY (circa 4.500 km2 o 1.700 sq mi) si sovrappone ancora al Woomera Test Range.
Il contratto di locazione per Mintabie è durato 21 anni, scadendo nel 2002. Una nuova legislazione nel 2009 ha permesso un altro contratto di locazione, che è stato firmato nell'aprile 2012.
