A GPR survey was carried out in advance of archaeological excavations at Madjedbebe (formerly known as Malakunanja II), a sandstone rock shelter in western Arnhem Land (Australia) containing numerous Aboriginal burials. GPR revealed subsurface patterning of rocks in the shelter deposits and archaeological excavation demonstrated that these were related to burials. Post-excavation, GIS and statistical analysis further elucidated the relationship between the rocks and human burials. This integration of detailed mapping, GPR and excavation afforded the opportunity to test a way to identify unmarked burials using GPR in sandstone rock shelters and to document a marker for burial identification in this region. Application of the methodology developed through this case study provides a useful management tool for Indigenous communities and other heritage practitioners.